8c_applications_of

Using row reduction (GJE) not only we can the rref of a given matrix $A$, but we can find a matrix $M$, as indicated in Notes 8, that $MA =$ rref$(A)$. Let us illustrate this by working out Checkpoint 2 in Notes 8.

In [1]:

%display latex
latex.matrix_delimiters(left='[',right=']')
A = matrix([[-2,-2,1,3,-1],[0,0,-1,1,0],[2,4,-1,-3,-2],[2,3,-1,-3,-2]]); A

Out[1]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\begin{array}{rrrrr} -2 & -2 & 1 & 3 & -1 \\ 0 & 0 & -1 & 1 & 0 \\ 2 & 4 & -1 & -3 & -2 \\ 2 & 3 & -1 & -3 & -2 \end{array}\right]$

To find such an $M$, as shown in Notes 8, we need to attach an identity matrix of the right size, in this case, a $4\times 4$, then find the rref of the resulting matrix.

In [2]:

I4 = identity_matrix(4); B = block_matrix([A,I4],ncols=2); B

Out[2]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\begin{array}{rrrrr|rrrr} -2 & -2 & 1 & 3 & -1 & 1 & 0 & 0 & 0 \\ 0 & 0 & -1 & 1 & 0 & 0 & 1 & 0 & 0 \\ 2 & 4 & -1 & -3 & -2 & 0 & 0 & 1 & 0 \\ 2 & 3 & -1 & -3 & -2 & 0 & 0 & 0 & 1 \end{array}\right]$

In [3]:

R = B.rref(); R #the right half of the rref of AI is a matrix M so that MA = rref(A)

Out[3]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\begin{array}{rrrrr|rrrr} 1 & 0 & 0 & -2 & 0 & -\frac{1}{3} & -\frac{1}{2} & -\frac{7}{6} & \frac{4}{3} \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & -1 \\ 0 & 0 & 1 & -1 & 0 & 0 & -1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & -\frac{1}{3} & 0 & \frac{1}{3} & -\frac{2}{3} \end{array}\right]$

Let's extract that right-half using the command matrix_from_columns

In [4]:

M = R.matrix_from_columns([5..8]); M

Out[4]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\begin{array}{rrrr} -\frac{1}{3} & -\frac{1}{2} & -\frac{7}{6} & \frac{4}{3} \\ 0 & 0 & 1 & -1 \\ 0 & -1 & 0 & 0 \\ -\frac{1}{3} & 0 & \frac{1}{3} & -\frac{2}{3} \end{array}\right]$

In [5]:

M*A, A.rref(), M*A==A.rref()

Out[5]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\left[\begin{array}{rrrrr} 1 & 0 & 0 & -2 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & -1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{array}\right], \left[\begin{array}{rrrrr} 1 & 0 & 0 & -2 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & -1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{array}\right], \mathrm{True}\right)$

Theorem. $A$ is invertible if and only if rref(A) is the identity matrix (of the same shape as $A$).

So the method above can be used to decide whether a square matrix $A$ is invertible and if so, find the inverse of $A$.

Again let's illustrate this by examples. Let $A$ be the following matrix.

In [6]:

%display latex
A = matrix(QQ,[[-1,-3,5],[3,-2,0],[-1,0,1]]); A

Out[6]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\begin{array}{rrr} -1 & -3 & 5 \\ 3 & -2 & 0 \\ -1 & 0 & 1 \end{array}\right]$

The tag along the identity matrix (of the right shape) to the right of $A$.

In [7]:

I3 = identity_matrix(3)

In [8]:

B = block_matrix([A,I3], ncols = 2); B

Out[8]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\begin{array}{rrr|rrr} -1 & -3 & 5 & 1 & 0 & 0 \\ 3 & -2 & 0 & 0 & 1 & 0 \\ -1 & 0 & 1 & 0 & 0 & 1 \end{array}\right]$

Certainly, finding the rref of $B$ is a simple call but this time let us we carry out GJE step-by-step to illustrate the algorithm.

In [9]:

B.rescale_row(0,-1); B

Out[9]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\begin{array}{rrr|rrr} 1 & 3 & -5 & -1 & 0 & 0 \\ 3 & -2 & 0 & 0 & 1 & 0 \\ -1 & 0 & 1 & 0 & 0 & 1 \end{array}\right]$

In [10]:

B.rescale_row(2,-1); B

Out[10]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\begin{array}{rrr|rrr} 1 & 3 & -5 & -1 & 0 & 0 \\ 3 & -2 & 0 & 0 & 1 & 0 \\ 1 & 0 & -1 & 0 & 0 & -1 \end{array}\right]$

In [11]:

B.add_multiple_of_row(2,0,-1); B

Out[11]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\begin{array}{rrr|rrr} 1 & 3 & -5 & -1 & 0 & 0 \\ 3 & -2 & 0 & 0 & 1 & 0 \\ 0 & -3 & 4 & 1 & 0 & -1 \end{array}\right]$

In [12]:

B.add_multiple_of_row(1,0,-3); B

Out[12]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\begin{array}{rrr|rrr} 1 & 3 & -5 & -1 & 0 & 0 \\ 0 & -11 & 15 & 3 & 1 & 0 \\ 0 & -3 & 4 & 1 & 0 & -1 \end{array}\right]$

In [13]:

B.rescale_row(1,-1/11); B

Out[13]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\begin{array}{rrr|rrr} 1 & 3 & -5 & -1 & 0 & 0 \\ 0 & 1 & -\frac{15}{11} & -\frac{3}{11} & -\frac{1}{11} & 0 \\ 0 & -3 & 4 & 1 & 0 & -1 \end{array}\right]$

In [14]:

B.add_multiple_of_row(2,1,3); B

Out[14]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\begin{array}{rrr|rrr} 1 & 3 & -5 & -1 & 0 & 0 \\ 0 & 1 & -\frac{15}{11} & -\frac{3}{11} & -\frac{1}{11} & 0 \\ 0 & 0 & -\frac{1}{11} & \frac{2}{11} & -\frac{3}{11} & -1 \end{array}\right]$

In [15]:

B.rescale_row(2,-11); B

Out[15]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\begin{array}{rrr|rrr} 1 & 3 & -5 & -1 & 0 & 0 \\ 0 & 1 & -\frac{15}{11} & -\frac{3}{11} & -\frac{1}{11} & 0 \\ 0 & 0 & 1 & -2 & 3 & 11 \end{array}\right]$

In [16]:

B.add_multiple_of_row(1,2,15/11); B

Out[16]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\begin{array}{rrr|rrr} 1 & 3 & -5 & -1 & 0 & 0 \\ 0 & 1 & 0 & -3 & 4 & 15 \\ 0 & 0 & 1 & -2 & 3 & 11 \end{array}\right]$

In [17]:

B.add_multiple_of_row(0,2,5); B

Out[17]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\begin{array}{rrr|rrr} 1 & 3 & 0 & -11 & 15 & 55 \\ 0 & 1 & 0 & -3 & 4 & 15 \\ 0 & 0 & 1 & -2 & 3 & 11 \end{array}\right]$

In [18]:

B.add_multiple_of_row(0,1,-3); B

Out[18]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\begin{array}{rrr|rrr} 1 & 0 & 0 & -2 & 3 & 10 \\ 0 & 1 & 0 & -3 & 4 & 15 \\ 0 & 0 & 1 & -2 & 3 & 11 \end{array}\right]$

After all these steps, we arrived to the rref of $B$ as above. So the left-half of the matrix is the rref of $A$. And we can see that it is the identity matrix. Thus, according the the theorem stated at the beginning, $A$ is invertible. Moreover, in that case, the left-half of $B$, as explained in class, is the inverse of $A$.

In [19]:

M = B.matrix_from_columns([3..5])

In [20]:

M*A, M ==A.inverse()

Out[20]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\left[\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right], \mathrm{True}\right)$

Our last example illustrates how this method can be use to tell if a matrix is not invertible. Let $A$ be the following matrix

In [21]:

A = matrix([[1,0,1],[-1,2,1],[1,2,3]]); A

Out[21]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\begin{array}{rrr} 1 & 0 & 1 \\ -1 & 2 & 1 \\ 1 & 2 & 3 \end{array}\right]$

In [23]:

AI = block_matrix([A,I3], ncols=2); AI, AI.rref()

Out[23]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\left[\begin{array}{rrr|rrr} 1 & 0 & 1 & 1 & 0 & 0 \\ -1 & 2 & 1 & 0 & 1 & 0 \\ 1 & 2 & 3 & 0 & 0 & 1 \end{array}\right], \left[\begin{array}{rrr|rrr} 1 & 0 & 1 & 0 & -\frac{1}{2} & \frac{1}{2} \\ 0 & 1 & 1 & 0 & \frac{1}{4} & \frac{1}{4} \\ 0 & 0 & 0 & 1 & \frac{1}{2} & -\frac{1}{2} \end{array}\right]\right)$

This time the left-half of rref($[A|I]$), which is rref($A$), is $\begin{bmatrix}1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 0\end{bmatrix}$, and is not an identity matrix. That means $A$ is not invertible.

Using Row Reduction¶

Finding inverses¶