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 \mathbf{x} which satisfies A\mathbf{x}=\mathbf{b}. This is easily seen to be a linear transformation, and its matrix will be denoted by A^{-1}, and called the inverse of A.

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}. We will use this in the following.

Proposition 4.1 Assume that A satisfies 1.-4. in Theorem 3.1. The following hold.

  1. A^{-1}A=AA^{-1}=I_n.
  2. A^{-1} also satisfies 1.-4. in Theorem 3.1.
  3. A is the inverse of A^{-1}.

We also say that A^{-1} is a left inverse of A when A^{-1}A=In, and a right inverse of A when AA^{-1}=I_n.

Proof. 1: Since clearly A^{-1}A\mathbf{x}=\mathbf{x} for all \mathbf{x}, and AA^{-1}\mathbf{b}=\mathbf{b} for all \mathbf{b}, we have that A^{-1}A=AA^{-1}=I_n.

2: Consider the system A^{-1}\mathbf{x}=\mathbf{0}. Multiplying with A on both sides and using 1. implies that \mathbf{x}=\mathbf{0}, so that A^{-1} satisfies 2. in Theorem 3.1. But then A satisfies all of 1.-4. as well.

3: Consider the linear transformation T which sends \mathbf{x} to the unique solution \mathbf{b} of the system A^{-1}\mathbf{b}=\mathbf{x}. Since then A\mathbf{x}=\mathbf{b}, we have that T(\mathbf{x})=\mathbf{b}=A\mathbf{x}, so that the matrix of T is A. It follows that the inverse of A^{-1} is A. This concludes the proof.

We say that A is invertible when there exists a square matrix B so that BA=AB=I_n. When A satisfies 1.-4. in Theorem 3.1, we have shown that A is invertible (simply choose B=A^{-1}). The other way, we will show that, if A is invertible, it must satisfy 1.-4. in Theorem 3.1. We will actually prove the following stronger statement:

Proposition 4.2 If AB=I_n, then both A and B satisfy 1.-4. in Theorem 3.1 (so that they are invertible). Also, A and B are inverses of one-another:

From this it follows that a left inverse is automatically a right inverse as well, and that inverses are unique.

Proof. If AB=I_n, Multiplying with A to the left on both sides in B\mathbf{x}=\mathbf{0} implies that \mathbf{x}=\mathbf{0} is the unique solution to this system, so that B satisfies 2. in Theorem 3.1, and hence all of 1.-4. as well. B thus has an inverse.

If we multiply the expression AB=I_n with B^{-1} to the right on both sides we obtain that A=B^{-1}. It follows that A also satisfies 1.-4..

If we multiply the expression A=B^{-1} with B to the right and A^{-1} to the left we obtain that B=A^{-1}, so that A and B are inverses of one-another.

We 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.

Some properties of the inverse matrix follow immediately from the definition. For instance, 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.

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:

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.3 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}. Let us verify the result in three different ways. First we verify with the built-in function for computing the inverse:

Then we verify symbolically:

Finally we verify with the method gaussian_elimination, which we implemented:

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).

Suppose now that all generators are distinct. We will prove by induction on n that all Vandermonde matrices are invertible. This is a bit more complicated. We know that a matrix is invertible if and only if its transpose is (see Exercise 4.3). Therefore it is enough to show that \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}. is invertible. It is clear that such 1\times 1 matrices are invertible - they are simply equal to (1). Suppose now that all such matrices of dimension n\times n, (n-1)\times(n-1),…,1\times 1 have been shown to be invertible. To show that an (n+1)\times(n+1) matrix on this form is invertible, we will apply elementary row operations, to end up with a matrix easily seen to be invertible. Since elementary row operations preserve invertibility, it follows that the matrix we started with is invertible as well. We start by subtracting x_0 times row i-1 from row i (for i=n,n-1,...,2). This zeros everything below the leading one in the upper left corner, and we obtain \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} This is clearly invertible if and only if \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, and this is the case if and only if its transpose \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. Dividing the first row by x_1-x_0, the second by x_2-x_0, and so on, we end up with the n\times n Vandermonde matrix \begin{pmatrix} 1 & x_1 & \cdots & x_1^{n-1} \\ \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & \cdots & x_n^{n-1} \end{pmatrix} 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 it 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: Let B the matrix with components b_{kn}=\frac{1}{N}e^{2\pi ikn/N}. We compute (F_NB)_{kl} = \sum_{n=0}^{N-1} (F_N)_{kn}B_{nl} = \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 the formula for the sum of a geometric series gives \frac{1-e^{2\pi i(l-k)}}{1-e^{2\pi i(l-k)/N}}=0. It follows that F_NB=I_N, so that B=(F_N)^{-1}. Since B differs from F_N by a conjugation, and a division by N in all entries, we have that B=F_N^{-1}=\frac{1}{N}\overline{F_N}, where \overline{F_N} is the matrix where all entries in F_N have been conjugated. \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
  1. 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?

  1. 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.
  1. 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.