Matrix equation and matrix inverse

The system of linear equations can be written in many different forms. In this course we discuss only some of them. The form that includes unknown variables $(x_1,x_2,\dots x_n)$ was already considered in the previous chapter.

$$\left\{ \begin{array}{ccccccccc} a_{11}x_{1}&+&a_{12}x_{2}&+... ...}x_{2}&+&\ldots &+&a_{mn}x_{n} & = & b_{m}, \end{array}\right.$$

Now we take a look at the matrix representation of this system. The following table of numbers is a matrix of the system.

$$A=\left( \begin{array}{cccc} a_{11} & a_{12} & \ldots & a_{1... ...vdots \\ a_{m1} & a_{m2} & \ldots & a_{mn} \end{array}\right)$$

The right hand side of the system is the following column.

$$b =\left( \begin{array}{c} b_{1},\\ b_{2},\\ \vdots \\ b_{m} \end{array}\right)$$

We use notations $A, b$ in order to write the system in matrix form. The string of unknowns $(x_1, x_2, \dots ,x_n)$ is denoted by $x$. We can treat $x$ as the following matrix.

$$x =\left( \begin{array}{c} x_{1},\\ x_{2},\\ \vdots \\ x_{n} \end{array}\right)$$

Now we define the multiplication between $A$ and $x$ such that

$$Ax = \left( \begin{array}{cccccccc} a_{11}x_{1}&+&a_{12}x_{... ..._{1}&+&a_{m2}x_{2}&+&\ldots &+&a_{mn}x_{n} \end{array}\right)$$

Then the system of linear equation can be written in the matrix form.

$$Ax =b.$$

This form is convenient for theoretical analysis of linear systems. Notice that the matrix $A$ has $m$ rows and $n$ columns ($m \times n$-matrix) while $x$ has $n$ rows and only one column ($n \times 1$-matrix). The result of their multiplication is $b$ that has $m$ rows and one column ($m \times 1$-matrix).

$$\begin{array}{cccc} \left( \begin{array}{cccc} a_{11} & a_{1... ...t)\\ (m \times n) & (n \times 1) && (m \times 1) \end{array}$$

As you can see the multiplication of $m \times n$ and $n \times 1$ matrices gives us an $m \times 1$ matrix. It is also true that the product of $m \times n$ and $n \times k$ matrices is an $m \times k$ matrix if the multiplication is defined as follows.

Definition 2.1   Given an $m \times n$ matrix $A$ and an $n \times k$ matrix $B$ then $A\cdot B$ is an $m \times k$ matrix defined as

$$A\cdot B = (A\cdot b^1\; A\cdot b^2 \dots A\cdot b^k),$$

where $b^1,\;b^2 ,\dots b^k$ are columns of $B.$

$\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \diamond$

$A\cdot B$ has $m$ rows and $k$ columns.

$$A\cdot b^j = \left( \begin{array}{cccccccc} a_{11}b_{1j}&+&... ...j}&+&a_{m2}b_{2j}&+&\ldots &+&a_{mn}b_{nj} \end{array}\right)$$

is its $j$-th column. The product $A\cdot B$ is defined only when the number of columns in $A$ is equal to the number of rows in $B.$ Moreover the product is associative. That means

$$(A\cdot B) \cdot C = A\cdot(B\cdot C)$$

as long as $(A\cdot B) \cdot C$ is defined.

Theorem 2.1   Let $A, B$ and $C$ be i $n\times m,\;\; m\times k,$ and $k\times \ell$ matrices, respectively. Then

$$(A\cdot B) \cdot C = A\cdot(B\cdot C)$$

Proof.

Let us show that $ij$-th entries of $(A\cdot B) \cdot C$ and $A\cdot(B\cdot C)$ are the same. Indeed,

$$A\cdot(B\cdot C)= A\cdot (B \cdot c^1 \; B \cdot c^2 \dots B \cdot c^\ell),$$

where $\ell$ is the number of columns in $C.$ For the $j$-th column we have

$$A\cdot (B \cdot c^j)= A\cdot \left( \begin{array}{cccccccc}... ...j}&+&b_{m2}c_{2j}&+&\ldots &+&b_{mn}c_{nj} \end{array}\right),$$

where $\{b_{ij}\}$ are entries for $B.$ Thus, $ij$-th entry for $A\cdot(B\cdot C)$ is

$$a_{i1}(b_{11}c_{1j}+b_{12}c_{2j}+\ldots +b_{1n}c_{nj} )+a_{i2}(b_{21}c_{1j}+b_{22}c_{2j}+\ldots +b_{2n}c_{nj} )+\ldots$$

$$+a_{in}(b_{n1}c_{1j}+b_{n2}c_{2j} +\ldots +b_{nk}c_{kj} )$$

Multiplication of real numbers is associative and we can group terms in () as follows.

$$(a_{i1} b_{11} + a_{i2} b_{21}+\dots a_{in} b_{n1})c_{1j} + (a_{i1} b_{12} + a_{i2} b_{22}+\dots a_{in} b_{n2})c_{2j}+\dots$$

$$(a_{i1} b_{1k} + a_{i2} b_{2k}+\dots a_{in} b_{nk})c_{kj}$$

This is the $i$-th entry of

$$(A\cdot b^1)\cdot c_{1j}+(A\cdot b^2)\cdot c_{2j}+ \dots + (A\cdot b^k)\cdot c_{kj}$$

which is the $j$-th column of $(A\cdot B)\cdot C.$

$\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \diamond$

Now we consider $n\times n$- matrices. They are called square. Some of the square matrices possess the following very important property - they might be invertible.

Definition 2.2   An $n\times n$- matrix $A$ is invertible if there exists an $n\times n$-matrix $A^{-1}$ such that

$$A\cdot A^{-1} = A^{-1} \cdot A = I_n,$$

where $I$ denotes the identity $n\times n$-matrix,

$$I_n= \left( \begin{array}{cccc} 1 & 0 & \ldots & 0 \\ 0 & 1... ...ts & \ddots & \vdots \\ 0 & 0 & \ldots & 1 \end{array}\right)$$

that has all entries outside its diagonal equal to zero while on the diagonal they are equal to $1.$ $A^{-1}$ is called the inverse of $A.$

$\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \diamond$

If the inverse $A^{-1}$ exists then the solution for the matrix equation

$$A\cdot x = b$$

is given by

$$x = A^{-1} b$$

Indeed, after using $A^{-1}b$ instead of $x$ in $Ax=b$ we obtain

$$A\cdot (A^{-1}b) = (A\cdot A^{-1})b= I\cdot b =b$$

Notice that

$$A\cdot (A^{-1}b) = (A\cdot A^{-1})b$$

follows from the fact that the matrix multiplication is associative, Theorem .

Given a $n\times n$- matrix $A$ there is a simple and efficient algorithm of calculating its inverse $A^{-1}.$

Algorithm for finding the inverse of a square matrix $A$

i.

Write the augmented matrix

$$(A \vert I_n),$$

where $n$ is the number of rows (columns) in $A.$

ii.

Try to convert $A$ into $I_n$ by the elementary row operations (see Chapter 1) where the rows are from $(A \vert I_n).$

iii.

If it is possible to convert $A$ into $I_n,$ then the augmented matrix takes the form $(I_n \vert A^{-1}).$

In other words, you need to play a game with $(A \vert I_n)$ the goal of the game is to bring $A$ into $I_n$ by using only elementary row operations. If it is possible to make $I_n$ out of $A,$ then $A$ is invertible and as soon as $A$ becomes $I_n$ the augmented matrix $(A \vert I_n)$ becomes $(I_n \vert A^{-1}).$

Example 2.1  

Find the inverse $A^{-1}$ of the matrix

$$A= \left( \begin{array}{cc} 1 & 2 \\ 3 & 1 \end{array}\right),$$

if $A^{-1}$ exists.

Solution. We start by writing the augmented matrix $(A \vert I_2),$

$$(A \vert I_2) = \left(\begin{array}{cc} 1 & 2 \\ 3 & 1 \en... ...t \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array}\right. \right)$$

After replacing the second row by its sum with the first row multiplied by $-3$ the matrix becomes

$$(A \vert I_2) = \left(\begin{array}{cc} 1 & 2 \\ 0 & -5 \... ...\begin{array}{cc} 1 & 0 \\ -3 & 1 \end{array}\right. \right).$$

Dividing the second row by $-5$ brings it into the form

$$(A \vert I_2) = \left(\begin{array}{cc} 1 & 2 \\ 0 & 1 \e... ...& 0 \\ \frac{3}{5} & -\frac{1}{5} \end{array}\right. \right).$$

Replacing the first row by its sum with the second row multiplied by $-2$ leads us to the following matrix.

$$(A \vert I_2) = \left(\begin{array}{cc} 1 & 0 \\ 0 & 1 \e... ...}{5} \\ \frac{3}{5} & -\frac{1}{5} \end{array}\right. \right)$$

The algorithm is completed. As you can see $A$ is invertible and its inverse is

$$A^{-1}=\left( \begin{array}{cc} -\frac{1}{5} & -\frac{2}{5} \\ \frac{3}{5} & -\frac{1}{5} \end{array}\right).$$

$\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \diamond$

To transform a square matrix $A$ into the identity $I_n$ one can start with Gaussian Elimination Procedure and try to bring $A$ into a triangular form. If $A$ can be made triangular with all elements on the diagonal not zeroes, then $A$ is invertible and moving upwards from the last row one can "kill" all elements above the diagonal. We illustrate this idea with the following example.

Example 2.2  

Find the inverse of

$$A=\left( \begin{array}{ccc} 2 & 3 & 4 \\ 1 & 1 & 1 \\ 1 & 4 & 9 \end{array}\right).$$

Solution. The augmented matrix $(A\vert I_3)$ has the following form.

$$(A\vert I_3)=\left( \begin{array}{ccc} 2 & 3 & 4 \\ 1 & 1 &... ... 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right. \right).$$

Now we apply Gaussian Elimination Procedure in order to bring $A$ into a triangular form. After interchanging the first and the second row we have

$$\left( \begin{array}{ccc} 1 & 1 & 1 \\ 2 & 3 & 4 \\ 1 & 4 ... ... 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{array}\right. \right).$$

We replace the second and the third row by their sums with the first row multiplied by $-2$ and $-1,$ respectively.

$$\left( \begin{array}{ccc} 1 & 1 & 1 \\ 0 & 1 & 2 \\ 0 & 3 ... ... & 0 \\ 1 & -2 & 0 \\ 0 & -1 & 1 \end{array}\right. \right).$$

Replacing the third row by its sum with the second row multiplied by $-3$ gives us the following matrix.

$$\left( \begin{array}{ccc} 1 & 1 & 1 \\ 0 & 1 & 2 \\ 0 & 0 ... ... & 0 \\ 1 & -2 & 0 \\ -3 & 5 & 1 \end{array}\right. \right).$$

We already have transformed $A$ into a triangular form. That means $A$ is invertible. To calculate $A-1$ we have to zero all elements above the diagonal. We start with the last row and eliminate all elements above $2.$ Subtracting the last row from the second leads us to

$$\left( \begin{array}{ccc} 1 & 1 & 1 \\ 0 & 1 & 0 \\ 0 & 0 ... ...& 0 \\ 4 & -7 & -1 \\ -3 & 5 & 1 \end{array}\right. \right).$$

Divide the third row by $2$ and then substract from the first row.

$$\left( \begin{array}{ccc} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 ... ...frac{3}{2} & \frac{5}{2} & \frac12 \end{array}\right. \right).$$

Finally, subtracting the second row from the first gives us

$$\left( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 ... ...frac{3}{2} & \frac{5}{2} & \frac12 \end{array}\right. \right).$$

The inverse matrix is calculated,

$$A^{-1}=\left( \begin{array}{ccc} -\frac{5}{2} & \frac{11}{2}... ...1 \\ -\frac{3}{2} & \frac{5}{2} & \frac12 \end{array}\right).$$

$\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \diamond$