4  The inverse matrix

We have seen that a system \(A\mathbf{x}=\mathbf{b}\) can be solved by Gaussian elimination. If \(A\) is square and satisfies 1.-4. in Theorem 3.1, we can consider the mapping \(\mathbf{b}\to\mathbf{x}\), i.e., the mapping which sends a given right hand side to the unique solution \(\mathbf{x}\). This is easily seen to be a linear transformation, and its matrix will be denoted by \(A^{-1}\). If we have found \(A^{-1}\), we can solve any system \(A\mathbf{x}=\mathbf{b}\) simply by computing \(\mathbf{x}=A^{-1}\mathbf{b}\).

In this chapter we shall define the inverse matrix more precisely. We will start by proving the following:

Lemma 4.1 Le \(A\) be a square matrix. \(A\) satisfies 1.-4. in Theorem 3.1 if and only if there exists a matrix \(B\) so that \(AB=I_n\).

Proof. Suppose that \(A=E_k\cdots E_1\) satisfies 1.-4. in Theorem 3.1. If \(F_i\) are elementary matrices which represent the reverse operations we have that \[E_k\cdots E_1F_1\cdots F_k=I_n.\] The matrix \(B=F_1\cdots F_k\) thus satisfies \(AB=I_n\). The other way, suppose \(A\) and \(B\) are square matrices so that \(AB=I_n\). Suppose that \(B\mathbf{x}=\mathbf{0}\) for an \(\mathbf{x}\neq 0\). Then \(AB\mathbf{x}=\mathbf{0}\) also, which violates that \(AB=I_n\). \(B\mathbf{x}=\mathbf{0}\) therefore has the unique solution \(\mathbf{x}=\mathbf{0}\), so that \(B\) satisfies 1.-4. in Theorem 3.1. But then \(B\) can be written as a product of elementary matrices, \(B=F_1\cdots F_k\). From \(AB=I_n\) it follows that \(A=E_k\cdots E_1\), where \(E_i\) represents the reverse row operations. \(A\) thus satisfies 1.-4. in Theorem 3.1 også.

When \(AB=I_n\) we say that \(B\) is a right inverse of \(A\). Due to the lemma above we can add that \(A\) has a right inverse as an equivalence in Theorem 3.1. We will do this, but with a small modification: We say that \(B\) is a left inverse of \(A\) if \(BA=I_n\). Suppose \(A\) has a right inverse \(B\). From the reasoning above it follows that we can write \(A=E_k\cdots E_1\) and \(B=F_1\cdots F_k\), where the \(E_i\) are elementary, and where the \(F_i\) are the reverse counterparts. But then \[BA = F_1\cdots F_kE_k\cdots E_1=I_n,\] so that \(B\) also is a left inverse of \(A\). It also follows that a left/right inverse is unique. We have shown the following.

Proposition 4.1 Suppose that \(B\) is a right inverse of \(A\). Then \(B\) is also a left inverse to \(A\). A left inverse/right inverse of \(A\) is unique.

Due to this we need not differ between right- and left inverses, and it is natural to define that \(A\) is invertible when there exists a matrix \(B\) so that \(AB=BA=I_n\). \(B\) is called the inverse matrix of \(A\), and we write \(A^{-1}\) for this.

Some properties of the inverse matrix follow immediately from the definition. Since \(A^{-1}A=I_n\), in particular \(\left(A^{-1}\right)^{-1}=A\). Furthermore, if \(s\neq 0\) then \[\left(sA\right)\left(s^{-1}A^{-1}\right)=AA^{-1}=I_n,\] so that \((sA)^{-1}=s^{-1}A^{-1}\). In the exercises of this chapter you will be asked to prove other properties of the inverse matrix.

Let us now extend Theorem 3.1 with an equivalence concerning invertibility, and at the same time give it a name.

Theorem 4.1 (Invertible matrix theorem) The following are equivalent for an \(n\times n\)-matrix \(A\):

1. \(A\) is row equivalent with \(I_n\).
2. \(A\mathbf{x}=\mathbf{0}\) has \(\mathbf{x}=\mathbf{0}\) as the only solution.
3. \(A\mathbf{x}=\mathbf{b}\) has a unique solution for all right hand sides \(\mathbf{b}\).
4. \(A\) can be written as a product of elementary matrices.
5. \(A\) is invertible.

From the discussion above it is also clear that if \(E_1,E_2,...,E_k\) are elementary matrices which row reduce \(A\) to the identity matrix
(so that \(E_k\cdots E_1A=I_n\)), then \[\begin{align*} A &= F_1\cdots F_k & A^{-1} &= E_k\cdots E_1 \end{align*}\] where \(F_i=E_i^{-1}\). In other words:

• \(A^{-1}\) can be obtained by multiplying the elementary matrices,
• \(A\) can be obtained by multiplying their inverses in reverse order.

To compute \(A^{-1}\) it is useful to apply the row operations not only on \(A\), but also on the augmented matrix \(\begin{pmatrix} A & I_n \end{pmatrix}\). Then we get \[E_k\cdots E_1\begin{pmatrix} A & I_n \end{pmatrix} = \begin{pmatrix} I_n & E_k\cdots E_1 \end{pmatrix} = \begin{pmatrix} I_n & A^{-1} \end{pmatrix}.\] From the result we can read out \(A^{-1}\) from the last columns. There is an alternative way to interpret this: when row reducing \(\begin{pmatrix} A & I_n \end{pmatrix}\), we simultaneously solve the systems \[\begin{align*} A\mathbf{x}_1&=\mathbf{e}_1 & A\mathbf{x}_2&=\mathbf{e}_2 & \cdots & \cdots & A\mathbf{x}_n&=\mathbf{e}_n, \end{align*}\] and since \(A\mathbf{x}_i=\mathbf{e}_i\) implies that \(A^{-1}\mathbf{e}_i=\mathbf{x}_i\), column \(i\) in \(A^{-1}\) will be \(\mathbf{x}_i\). Let us summarise.

Proposition 4.2 Suppose that \(A\) is invertible. The reduced echelon form of \(\begin{pmatrix} A & I_n \end{pmatrix}\) equals \(\begin{pmatrix} I_n & A^{-1} \end{pmatrix}\).

Example 4.1 Let us find the inverse matrix of \(A=\begin{pmatrix} 2 & 3 & 1 \\ 1 & 4 & 1 \\ 2 & 4 & 2 \end{pmatrix}\): \[\begin{align*} \begin{pmatrix} A & I_n \end{pmatrix}&=\begin{pmatrix} 2 & 3 & 1 & 1 & 0 & 0 \\ 1 & 4 & 1 & 0 & 1 & 0 \\ 2 & 4 & 2 & 0 & 0 & 1 \end{pmatrix} \stackrel{I\leftrightarrow II}{\sim} \begin{pmatrix} 1 & 4 & 1 & 0 & 1 & 0 \\ 2 & 3 & 1 & 1 & 0 & 0 \\ 2 & 4 & 2 & 0 & 0 & 1\end{pmatrix} \\ &\stackrel{II-2I}{\sim} \begin{pmatrix} 1 & 4 & 1 & 0 & 1 & 0 \\ 0 & -5 & -1 & 1 & -2 & 0 \\ 2 & 4 & 2 & 0 & 0 & 1 \end{pmatrix} \stackrel{III-2I}{\sim} \begin{pmatrix} 1 & 4 & 1 & 0 & 1 & 0 \\ 0 & -5 & -1 & 1 & -2 & 0 \\ 0 & -4 & 0 & 0 & -2 & 1 \end{pmatrix} \\ &\stackrel{II\leftrightarrow III}{\sim} \begin{pmatrix} 1 & 4 & 1 & 0 & 1 & 0 \\ 0 & -4 & 0 & 0 & -2 & 1 \\ 0 & -5 & -1 & 1 & -2 & 0 \end{pmatrix} \stackrel{II/(-4)}{\sim} \begin{pmatrix} 1 & 4 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1/2 & -1/4 \\ 0 & -5 & -1 & 1 & -2 & 0 \end{pmatrix} \\ &\stackrel{III+5II}{\sim} \begin{pmatrix} 1 & 4 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1/2 & -1/4 \\ 0 & 0 & -1 & 1 & 1/2 & -5/4 \end{pmatrix} \stackrel{III(-1)}{\sim} \begin{pmatrix} 1 & 4 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1/2 & -1/4 \\ 0 & 0 & 1 & -1 & -1/2 & 5/4 \end{pmatrix} \\ &\stackrel{I-III}{\sim} \begin{pmatrix} 1 & 4 & 0 & 1 & 3/2 & -5/4 \\ 0 & 1 & 0 & 0 & 1/2 & -1/4 \\ 0 & 0 & 1 & -1 & -1/2 & 5/4 \end{pmatrix} \stackrel{I-4II}{\sim} \begin{pmatrix} 1 & 0 & 0 & 1 & -1/2 & -1/4 \\ 0 & 1 & 0 & 0 & 1/2 & -1/4 \\ 0 & 0 & 1 & -1 & -1/2 & 5/4 \end{pmatrix}. \end{align*}\] We read out the last 3 columns as \(A^{-1}=\begin{pmatrix} 1 & -1/2 & -1/4 \\ 0 & 1/2 & -1/4 \\ -1 & -1/2 & 5/4 \end{pmatrix}\). We can verify the result with the built-in function for computing the inverse:

np.linalg.inv([[2,3,1],[1,4,1],[2,4,2]])

array([[ 1.  , -0.5 , -0.25],
       [ 0.  ,  0.5 , -0.25],
       [-1.  , -0.5 ,  1.25]])

We can also verify the answer symbolically:

sym.Matrix([[2,3,1],[1,4,1],[2,4,2]]).inv()

\(\displaystyle \left[\begin{matrix}1 & - \frac{1}{2} & - \frac{1}{4}\\0 & \frac{1}{2} & - \frac{1}{4}\\-1 & - \frac{1}{2} & \frac{5}{4}\end{matrix}\right]\)

We can also read out the elementary matrices \[\begin{align*} E_1 &= \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{pmatrix} & E_2 &= \begin{pmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1\end{pmatrix} & E_3 &= \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -2 & 0 & 1 \end{pmatrix} & E_4 &= \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} \\ E_5 &= \begin{pmatrix} 1 & 0 & 0 \\ 0 & -1/4 & 0 \\ 0 & 0 & 1 \end{pmatrix} & E_6 &= \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 5 & 0 & 1\end{pmatrix} & E_7 &= \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 &-1\end{pmatrix} & E_8 &= \begin{pmatrix} 1 & 0 & -1 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{pmatrix} \\ E_9 &= \begin{pmatrix} 1 & -4 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \end{align*}\] and \[\begin{align*} F_1 &= \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{pmatrix} & F_2 &= \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 0 & 1\end{pmatrix} & F_3 &= \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 2 & 0 & 1 \end{pmatrix} & F_4 &= \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} \\ F_5 &= \begin{pmatrix} 1 & 0 & 0 \\ 0 & -4 & 0 \\ 0 & 0 & 1 \end{pmatrix} & F_6 &= \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -5 & 0 & 1\end{pmatrix} & F_7 &= \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 &-1\end{pmatrix} & F_8 &= \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{pmatrix} \\ F_9 &= \begin{pmatrix} 1 & 4 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \end{align*}\] With these we have that \(A^{-1}=E_9\cdots E_1\), and \(A=F_1\cdots F_9\). \(\clubsuit\)

Example 4.2 Consider the system \(A\mathbf{x}=\mathbf{b}\) with \(A=\begin{pmatrix} 2 & 3 & 1 \\ 1 & 4 & 1 \\ 2 & 4 & 2 \end{pmatrix}\) from the preceding example, and where \(\mathbf{b}=\begin{pmatrix} 19 \\ 21 \\ 26 \end{pmatrix}\). We found \(A^{-1}\) above. If we use this we see that the solution to the system above is \[ \mathbf{x}=A^{-1}\mathbf{b} = \begin{pmatrix} 1 & -1/2 & -1/4 \\ 0 & 1/2 & -1/4 \\ -1 & -1/2 & 5/4 \end{pmatrix}\begin{pmatrix} 19 \\ 21 \\ 26 \end{pmatrix} = \begin{pmatrix} 19-21/2-13/2 \\ 21/2-13/2 \\ -19 -21/2 + 65/2 \end{pmatrix} = \begin{pmatrix} 2 \\ 4 \\ 3 \end{pmatrix}. \] The system can also be solved by Gaussian elimination on the augmented matrix \(\begin{pmatrix} A & \mathbf{b}\end{pmatrix}\). This is preferable, since Gaussian elimination on \(\begin{pmatrix} A & I_n \end{pmatrix}\) requires more computation than that on \(\begin{pmatrix} A & \mathbf{b} \end{pmatrix}\) (there are fewer columns in this matrix). \(\clubsuit\)

Example 4.3 (Square Vandermonde matrices are invertible) Let us prove that the Vandermonde matrix \[ \begin{pmatrix} 1 & x_0 & x_0^2 & \cdots & x_0^n \\ 1 & x_1 & x_1^2 & \cdots & x_1^n \\ 1 & x_2 & x_2^2 & \cdots & x_2^n \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & x_n^2 & \cdots & x_n^n \end{pmatrix} \tag{4.1}\] is invertible if and only if the generators \(x_0,x_1,\dots,x_n\) are distinct. One direction of the proof is easy: If two of the generators are equal, then two of the rows are equal, and then \(A\) can’t be invertible (Exercise 4.4). The other way is a bit more complicated.

Suppose now that all generators are distinct. We will prove by induction on \(n\) that the Vandermonde matrix is invertible. It is clear that \(1\times 1\) Vandermonde matrices are invertible, since they are simply equal to \((1)\). Suppose now that all square Vandermonde matrices of dimension \(n\times n\), \((n-1)\times(n-1)\),…,\(1\times 1\) have been shown to be invertible. To show that all \((n+1)\times(n+1)\)-matrices are invertible it is enough to show that their transposes are invertible (Exercise 4.3). So, consider the matrix \[ \begin{pmatrix} 1 & 1 & \cdots & 1 \\ x_0 & x_1 & \cdots & x_n \\ x_0^2 & x_1^2 & \cdots & x_n^2 \\ \vdots & \vdots & \ddots & \vdots \\ x_0^n & x_1^n & \cdots & x_n^n \end{pmatrix}. \] We now subtract \(x_0\) times row \(i-1\) from row \(i\) (for \(i=n,n-1,...,2\)). This zeros everything under the leading one in the upper left corner, and does not change whether the matrix is invertible or not. It therefore holds to show that \[ \begin{pmatrix} 1 & 1 & \cdots & 1 \\ 0 & x_1-x_0 & \cdots & x_n -x_0 \\ 0 & x_1(x_1-x_0) & \cdots & x_n(x_n-x_0) \\ \vdots & \vdots & \ddots & \vdots \\ 0 & x_1^{n-1}(x_1-x_0) & \cdots & x_n^{n-1}(x_n-x_0) \end{pmatrix} \] is invertible. But this is the same as that \[ \begin{pmatrix} x_1-x_0 & \cdots & x_n -x_0 \\ x_1(x_1-x_0) & \cdots & x_n(x_n-x_0) \\ \vdots & \ddots & \vdots \\ x_1^{n-1}(x_1-x_0) & \cdots & x_n^{n-1}(x_n-x_0) \end{pmatrix} \] is invertible, which is the same as that \[ \begin{pmatrix} x_1-x_0 & x_1(x_1-x_0) & \cdots & x_1^{n-1}(x_1-x_0) \\ \vdots & \vdots & \ddots & \vdots \\ x_n-x_0 & x_n(x_n-x_0) & \cdots & x_n^{n-1}(x_n-x_0) \end{pmatrix} \] is invertible (Exercise 4.3 again). We now apply more row operations: The first row is multiplied with \(1/(x_1-x_0)\) the second row with \(1/(x_2-x_0)\), and so on. After having done this we see that it is enough to show that \[ \begin{pmatrix} 1 & x_1 & \cdots & x_1^{n-1} \\ \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & \cdots & x_n^{n-1} \end{pmatrix} \] is invertible. But this is an \(n\times n\) Vandermonde matrix, which we assumed to be invertible. This completes the proof. \(\clubsuit\)

Example 4.4 (The Fourier matrix) The Fourier matrix is also a Vandermonde matrix, so that this is invertible as well. While we don’t have a general expression for the inverse of a Vandermonde matrix, the situation is different for the Fourier matrix: We claim that the inverse matrix has components \(\frac{1}{N}e^{2\pi ikn/N}\). We have that \[\sum_{n=0}^{N-1} e^{-2\pi ikn/N}\frac{1}{N}e^{2\pi inl/N}=\frac{1}{N}\sum_{n=0}^{N-1} e^{2\pi in(l-k)/N}.\] If \(l=k\) this is \(1\). If \(l\neq k\) we can use the sum formula for a geometric series to get \[\frac{1-e^{2\pi i(l-k)}}{1-e^{2\pi i(l-k)/N}}=0.\] It follows that the inverse matrix has components \(\frac{1}{N}e^{2\pi ikn/N}\), so that \((F_N)^{-1}=\frac{1}{N}\overline{F_N}\). \(\clubsuit\)

Quiz

--- primary_color: orange secondary_color: lightgray text_color: black shuffle_questions: false shuffle_answers: false --- ## Matching dimensions in matrix multiplication Let $A\in\mathbb{R}^{3\times 5}$ and $B\in \mathbb{R}^{6\times 3}$. Which of the following statements are correct? > We have $A^T\in\mathbb{R}^{5\times 3}$ and $B\in\mathbb{R}^{6\times 3}$, so that $A^T$ does not have as many columns (3) as $B$ has rows (6). 1. [ ] The product $AB$ is defined. 1. [ ] The equation $BA=C$ has the solution $A=B^{-1}C$. 1. [ ] The matrix $B$ has double as many components as $A$. 1. [x] The product $A^TB$ is not defined. 1. [ ] None of the other statements are true. ## Inverse of a matrix The inverse of the matrix $$\begin{pmatrix} 1 & 0 & 3 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$$ is 1. [ ] $$\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -3 & 0 & 1 \end{pmatrix}$$ 1. [ ] $$\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 3 & 0 & 1 \end{pmatrix}$$ 1. [x] $$\begin{pmatrix} 1 & 0 & -3 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$$ ## Inverse of a matrix The inverse matrix of $$\begin{pmatrix} 1/2 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & -1 \end{pmatrix}$$ 1. [x] is $$\begin{pmatrix} 2 & 0 & 0 \\ 0 & 1 /2& 1/2 \\ 0 & 1/2 & -1/2 \end{pmatrix}$$ 2. [ ] does not exist 3. [ ] is $$\begin{pmatrix} 2 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & -1 \end{pmatrix}$$

Exercises

Exercise 4.1 In this exercise we set \(A=\begin{pmatrix} 2 & -1 & 1 \\ 0 & 1 & 4 \\ 1 & -2 & -6\end{pmatrix}\)

1. Find the inverse matrix of \(A\)

2. Write \(A\) and \(A^{-1}\) as products of elementary matrices.

Exercise 4.2 (The inverse of \(2\times 2\)-matrices) Show that a general \(2\times 2\)-matrix \(\begin{pmatrix} a & b \\ c & d \end{pmatrix}\) is invertible if and only if \(ad-bc\neq 0\), and that the inverse is \(\frac{1}{ad-bc}\begin{pmatrix} d & -b \\ -c & a \end{pmatrix}\).

Exercise 4.3 (The transpose of an invertible matrix is invertible) Show that \(A\) is invertible if and only if \(A^T\) is invertible. Show that then \((A^{T})^{-1}=(A^{-1})^T\).

Exercise 4.4 Let \(A\) be a matrix with either a row or a column of zeros. Show that \(A\) is not invertible. Show also that the same conclusion holds if \(A\) has two equal rows or columns.

Exercise 4.5 (Products of invertible matrices are invertible) Suppose that \(A\) and \(B\) both are invertible \(n\times n\)-matrices. Show that \(AB\) also is invertible, and that \((AB)^{-1}=B^{-1}A^{-1}\).

Exercise 4.6 (Invertible matrices are ismorphisms) Let \(T:\mathbb{R}^n\to\mathbb{R}^n\) be a linear transformation. We say that \(T\) is \(1\to 1\) if \(T(\mathbf{x})\neq T(\mathbf{y})\) whenever \(\mathbf{x}\neq\mathbf{y}\). We also say that \(T\) is onto if, for any \(\mathbf{y}\in V\), there exists a \(\mathbf{x}\in U\) so that \(T(\mathbf{x})=\mathbf{y}\). Show that the matrix of \(T\) is invertible if and only if \(T\) is onto and \(1\to 1\). Linear transformations that are onto and \(1\to 1\) are also called isomorphisms.

Exercise 4.7 (Nilpotent matrices are not invertible) A square matrix \(A\) is called nilpotent if there exists a \(k>1\) so that \(A^k=0\). The smallest such \(k\) is called the index of nilpotence of \(A\).

1. Run the following code:

Is \(A\) nilpotent? If so, what is the index of nilpotence?

2. Show that nilpotent matrices are not invertible.

Exercise 4.8 (Triangular matrices and invertibility) A square matrix \(A\) is called upper-triangular if everything below the diagonal of \(A\) is \(0\), and lower-triangular if everything above the diagonal of \(A\) is \(0\). \(A\) is called triangular if it is either upper- or lower-triangular.

1. Show that a triangular matrix is invertible if and only if all elements on the diagonal are \(\neq 0\).

2. Suppose that \(A\) is invertible and upper/lower-triangular. Show that \(A^{-1}\) also is upper/lower-triangular.

Exercise 4.9 Let \(A\) be an invertible matrix. Write code which verifies that, when \(\mathbf{b}\) is a column vector, the commands np.linalg.solve(A,b) and np.linalg.inv(A)*b return the same.