System of linear equations and Inverse matrix

We have introduced Guassian elimination in 2.2. Here we study whether the given system of linear equation has a solution. To start with, we consider the system of linear equation with the unkowns and the number of equations are different.

$$\left\{\begin{array}{cccccc} a_{11}x_{1} &+& a_{12}x_{2}&+\cdots+... ... a_{m1}x_{1} &+& a_{m2}x_{2}&+\cdots+&a_{mn}x_{n}& = b_{m} \end{array}\right.$$

Let $A = (a_{ij})$ be a matrix, $[A : {\bf b}]$ be the augmented matrix, $n$ be the number of unknowns, ${\mathbf x} = (x_{j})$ be the row vectors, and ${\bf b} = (b_{i})$ be the column vetors of the order $m$. Then the system of linear equations is written as

$$A{\mathbf x} = {\bf b} \mbox{または} [A : {\bf b}]$$

When the solution to this system of equations exists, each solutions are considered as vectors ${\mathbf x}$ and this vector is called solution vector. In general, the following holds.

$${\rm rank}(A) \leq {\rm rank}([A : {\bf b}]) \leq {\rm rank}(A) + 1$$

Theorem 2..7  

The system of linear equation $A{\mathbf x} = {\bf b}$ has a solution if and only if

$${\rm rank}(A) = {\rm rank}([A : {\bf b}])$$

Proof Let $A$ be a matrix of the form $m \times n$. Suppose that ${\rm rank}(A) = {\rm rank}([A : {\bf b}]) = r$ . Then the dimension of the column space of $[A : {\bf b}]$ is $r$ and $r \leq n$. Thus, $n+1$st column vectorb of the column space $[A : {\bf b}]$ is a linear combination of

$${\bf a_{1}}, {\bf a_{2}}, \ldots, {\bf a_{n}}$$

Thus,

$${\bf a}_{1}c_{1} + {\bf a}_{2}c_{2} + \cdots + {\bf a}_{n}c_{n} = {\bf b}.$$

In other words,

$$A\left(\begin{array}{c} c_{1}\\ c_{2}\\ \vdots\\ c_{n} \end{array}\right) = {\bf b}.$$

Conversely, think of columns of $A$ as column vectors. Thne the equation $A{\mathbf x} = {\bf b}$ can be expressed as

$${\bf a}_{1}x_{1} + {\bf a}_{2}x_{2} + \cdots + {\bf a}_{n}x_{n} = {\bf b}$$

If there exist solutions such as $x_{1},x_{2},\ldots,x_{n}$, then this equation implies that ${\bf b}$ is a linear combination of

$${\bf a}_{1}, {\bf a}_{2}, \ldots, {\bf a}_{n}$$

Thus, the column space of $A$ and the column space of $[A : {\bf b}]$ are the same. This shows that ${\rm rank}(A) = {\rm rank}([A : {\bf b}])$. $\blacksquare$

Example 2..10  

Select the value of $k$ so that the following equation has a solution.

$$\left\{\begin{array}{ll} x+2y & = 3\\ 2x-z & = 2\\ 4y + z & = k \end{array}\right.$$

Answer

$$[A: {\bf b}] = \left(\begin{array}{cccc} 1&2&0&3\\ 2&0&-1&2\\ 0&4&1&k \end{arr... ...} \left(\begin{array}{cccc} 1&2&0&3\\ 0&-4&-1&-4\\ 0&4&1&k \end{array}\right)$$

$$\stackrel{\begin{array}{cc} {}^{R_{2} \leftrightarrow R_{3}}\\ {}^{R_{2} + R_{3}} \end{array}}{\longrightarrow} \left(\begin{array}{cccc} 1&2&0&3\\ 0&4&1&4\\ 0&0&0&k-4 \end{array}\right) .$$

A necessary and sufficient conditions for which this system of equations has a solution is ${\rm rank}([A: {\bf b}]) = {\rm rank}A = 2$. Thus $k - 4$ must be 0. Therefore $k = 4$. $\blacksquare$

$\spadesuit$General solution of system of linear equation $\spadesuit$

Theorem 2..8  

Let ${\bf p}$ be a pair of solution to the system of linear equations $A{\mathbf x} = {\bf b}$. Then every solution of $A{\mathbf x} = {\bf b}$ is given by ${\bf p} + {\bf c}$. Here, ${\bf c}$ is a solution of $A{\mathbf x} = {\bf0}$ .

Proof Let ${\bf w}$ be a solution of $A{\mathbf x} = {\bf b}$. Then, ${\bf w} - {\bf p}$ is a solution of $A{\mathbf x} = {\bf0}$ since

$$A({\bf w} - {\bf p}) = A{\bf w} - A{\bf p} = {\bf b} - {\bf b} = {\bf0}.$$

Next let ${\bf c} = {\bf w} - {\bf p}$. Then ${\bf c}$ is a solution of $A{\mathbf x} = {\bf0}$. Thus, we have ${\bf w} = {\bf p} + {\bf c}$. $\blacksquare$

With this theorem, to solve the system of linear equations $A{\mathbf x} = {\bf b}$, we first need to solve the homogeneous system $A{\mathbf x} = {\bf0}$. So, we consider the homogeneous system of linear equations $A{\mathbf x} = {\bf0}$.

Note that ${\rm rank}(A) = {\rm rank}([A : {\bf0}])$. Then by the theorem 2.3, a solution exists. In fact, $x_{1} = x_{2} = \cdots = x_{n} = 0$ is a solution. This solution is called trivial solution. Next Let $s$ numbers of nontrivial solutions of the system of linear equations be the followings:

$${\bf v}_{1} = \left(\begin{array}{c} v_{11}\\ v_{21}\\ \vdots\\... ...\left(\begin{array}{c} v_{1s}\\ v_{2s}\\ \vdots\\ v_{ms} \end{array}\right)$$

Then

$$A{\bf v}_{1} = {\bf0}, A{\bf v}_{2} = {\bf0}, \ldots , A{\bf v}_{s} = {\bf0}$$

Furthermore, a linear combination of these nontrivial solutions ${\mathbf x} = c_{1}{\bf v}_{1} + c_{2}{\bf v}_{2} + \cdots + c_{s}{\bf v}_{s}$ satisfies $A{\mathbf x} = c_{1}(A{\bf v}_{1}) + c_{2}(A{\bf v}_{2}) + \cdots + c_{s}(A{\bf v}_{s}) = 0$ Thus, $\langle{\bf0}, {\bf v}_{1}, {\bf v}_{2}, \ldots, {\bf v}_{s}\rangle$is a subspace. This subspace is called solution space. The basis of this solution space is called an (elementary solution of the system of linear equation $A{\mathbf x} = {\bf0}$.

It is interesting to know the relationship between the dimension of the solution space and the rank of the matrix.

Theorem 2..9  

Given a system of linear equations with $n$ unknowns $x_{1},x_{2},\ldots,x_{n}$. Suppose the rank of the coefficient matrix $A$ is $r$, then the fundamental solution is composed of the $n - r$ solution vectors.

Proof For ${\rm rank}(A) = {\rm rank}([A : {\bf0}]) = r$, apply the elementry row operation on $[A : {\bf0}]$ to obtain the followings:

$$[A : {\bf0}]_{R} = \left(\begin{array}{rrrrrrcr} 1&\cdots&0&d_{1 ... ...ts& &\vdots&\vdots&\vdots\\ 0&\cdots&0&0&\cdots&0&\vdots&0 \end{array}\right)$$

Here, let

$${\mathbf x}_{1} = \left(\begin{array}{c} -d_{1 r+1}\\ \vdots\\ ... ...c} -d_{1 n}\\ \vdots\\ -d_{r n}\\ 0\\ 0\\ \vdots\\ 1 \end{array}\right) .$$

Then, ${\mathbf x}_{1}, {\mathbf x}_{2}, \ldots , {\mathbf x}_{n-r}$ are solution vectors. Also, let

$$c_{1}{\mathbf x}_{1} + c_{2}{\mathbf x}_{2} + \cdots + c_{n-r}{\mathbf x}_{n-r} = {\bf0}$$

Then

$$c_{1}{\mathbf x}_{1} + c_{2}{\mathbf x}_{2} + \cdots + c_{n-r}{\m... ...begin{array}{c} 0\\ \vdots\\ 0\\ 0\\ 0\\ \vdots\\ 0 \end{array}\right).$$

From this, we have $c_{1} = c_{2} = \cdots = c_{n-r} = 0$. Thus, ${\mathbf x}_{1}, {\mathbf x}_{2}, \ldots , {\mathbf x}_{n-r}$ is linearly independent. Therefore the dimension of the solution space is $n - r$. $\blacksquare$

$\spadesuit$Degree of freedom $\spadesuit$

The number of elementary solutions $n - r$ is called a degree of freedom.

Example 2..11  

Solve the following system of linear equations:

$$\left\{\begin{array}{rr} x_{1}+x_{2}+2x_{3}+4x_{4}& = 3\\ 3x_{1}+x_{2}+6x_{3}+2x_{4}& = 3\\ -x_{1}+2x_{2}-2x_{3}+x_{4}& = 1 \end{array}\right.$$

Answer Apply Gaussian elimination..

$$[A: {\bf b}] = \left(\begin{array}{rrrrr} 1&1&2&4&3\\ 3&1&6&2&3\\ -1&2&-2&1&1 ... ...\begin{array}{rrrrr} 1&1&2&4&3\\ 0&-2&0&-10&-6\\ 0&3&0&5&4 \end{array}\right)$$

$$\rightarrow \left(\begin{array}{rrrrr} 1&0&2&-1&0\\ 0&1&0&5&3\\ 0&0&0&1&\fr... ...&0&0&\frac{1}{2}\\ 0&0&0&1&\frac{1}{2} \end{array}\right) = [A: {\bf b}]_{R} .$$

This shows that ${\rm rank}(A) = {\rm rank}([A : {\bf b}]) = 3$ which implies that this system of linear equation has a solution. If we write $[A:{\bf b}]_{R}$ as a system of linear equatios:

$$\left\{\begin{array}{rr} x_{1} + 2x_{3} & = \frac{1}{2}\\ x_{2} & = \frac{1}{2}\\ x_{4} & = \frac{1}{2} \end{array}\right.$$

Then $n = 4, r = 3$. Thus the defree of freedom is $1$. Then we let $x_{3} = \alpha$ and we have the followings:

$$\left(\begin{array}{c} x_{1}\\ x_{2}\\ x_{3}\\ x_{4} \end{arra... ...y}\right) + \alpha \left(\begin{array}{r} -2\\ 0\\ 1\\ 0 \end{array}\right)$$

$\blacksquare$

$\spadesuit$Inverse Matrix $\spadesuit$

Consider the matrix $A = \left(\begin{array}{rr} 1&0\\ 1&0 \end{array}\right)$. $A$ is not zeor matrix. Now we ask you a question. Do we have a matrix $X$ so that $AX = XA = I$. Unfortunately, the answer is no. In the world of matrices, some nonzero matrix does not have inverse.

$\spadesuit$Regular Matrix $\spadesuit$

For the square matrix $A$ of the order$n$, if there exists a matrix $X$ so that $XA = AX =I$, then the matrix $A$ is called a regular matrix. The matrix $X$ is called an inverse matrix of $A$. Now how many inverse matrices of $A$ exist? For example, $AX = XA = I, AZ = ZA = I$. Then $X = XI = X(AZ) = (XA)Z = IZ = Z$. Thus, the inverse matrix of $A$ is one. Then we write the inverse matrix of $A$ as $A^{-1}$.

Using this idea, we solve the system of linear equations $A{\mathbf x} = {\bf b}$. Let $A$ be a regular matrix. Then we have $A^{-1}(A{\mathbf x}) = A^{-1}{\bf b}$. From this, we have ${\mathbf x} = A^{-1}{\bf b}$. Therefore, to solve the system of linear equations, we can use the inverse matrix $A^{-1}$. In short, it is enough to find a matrix $X$ so that $AX = I$ We know a quick way to find $X$. Before introducing the technique, we cover the relation between the regular matrix and the rank of the matrix.

Theorem 2..10  

Suppose that the matrix $A$ is a squre matrix with the order of $n$. Then the followings are equivalent.
$(1) {\rm rank}(A) = n$
$(2) A$ is regular matrix.

Proof By theorem 2.2, ${\rm rank}(A) = n$ and $A_{R} = I$ are equivalent. In other words, for ${\rm rank}(A) = n$, we can choose the product of elementary matrices $P$ so that $PA = I$. Thus, $A$ is regular.

Conversely, for $A$ is a regular matrix, we can choose a product of elementary matrices $P$ so that $PA = A_{R}$. Note that $P$ is the product of elementary matrices. Then $P$ is regular. Thus, $P^{-1}$ exists. Suppose that $A_{R} \neq I$. Then the entries of the lowest row of $A_{R}$ have to be 0. But then this matrix is not regular. Thus, ${\rm rank}(A) = n$. $\blacksquare$

Now we are ready to introduce how to find a matrix $I$ satisfying $AX = I$. We note that since $A$ is regular, for some product $P$ of elementary matrices, $PA = I$. So, we multiply this $P$ to $AX = I$ from the left. Then $P(AX) = (PA)X = IX = X, PI = P$. Thus to find $X$ is the same as to find $P$. This shows that if you can get the identiry matrix by applying elementary row operation to $A$, the the same operation on $I$ gives rise to $A^{-1}$.

Example 2..12  

Determine whether the matrix $A$ is regular. If so, find the inverse matrix of $A$ where $A = \left(\begin{array}{rrr} 1&2&3\\ 2&-1&1\\ 4&3&2 \end{array}\right)$.

Answer

$$[A:I] = \left(\begin{array}{rrrrrr} 1&2&3&1&0&0\\ 2&-1&1&0&1&0\\ 4&3&2&... ...y}{rrrrrr} 1&2&3&1&0&0\\ 0&-5&-5&-2&1&0\\ 0&-5&-10&-4&0&1 \end{array}\right )$$

$$\longrightarrow \left(\begin{array}{rrrrrr} 1&2&3&1&\!\!0&\!\!0\\ 0&1&1&\frac{2}... ...rac{1}{5}&\!\!0\\ 0&1&2&\frac{4}{5}&\!\!0&\!\!-\frac{1}{5} \end{array}\right )$$

$$\longrightarrow \left(\begin{array}{rrrrrr} 1&0&0&-\frac{1}{5}&\frac{1}{5}&\frac{... ... 0&0&1&\frac{2}{5}&\frac{1}{5}&-\frac{1}{5} \end{array}\right ) = [I:A^{-1}] .$$

This shows that $A$ is regular and $A^{-1} = \left(\begin{array}{rrr} -\frac{1}{5}&\frac{1}{5}&\frac{1}{5}\\ 0&-\frac{2}{5}&\frac{1}{5}\\ \frac{2}{5}&\frac{1}{5}&-\frac{1}{5} \end{array}\right )$. $\blacksquare$

Summarize what we have studied so far, we have

Theorem 2..11  

Suppose that the matrix $A$ is the square matrix of the order $n$. Then the followings are equivalent.
$(1) A$ is regular
$(2) {\rm rank}(A) = n$
$(3) A_{R} = I$

Proof By theorem 2.2, we have $(2) \Leftrightarrow (3)$. By theorem 2.3, we have $(1) \Leftrightarrow (2)$.

Exercise2-6

1. Solve the following system of linear equations using Gaussian elimination.

(a) $\left\{\begin{array}{rrr} x-3y&=&5\\ 3x-5y&=&7 \end{array}\right .$

(b) $\left\{\begin{array}{rrr} x+y+z&=&3\\ x+2y+2z&=&5\\ x+2y+3z&=&6 \end{array}\right .$

(c) $\left\{\begin{array}{rrr} x_{1}+x_{2}+x_{3}+x_{4}&=&1\\ x_{1}+2x_{2}+3x_{3}+4x_{4}&=&2\\ x_{1}+4x_{2}+9x_{3}+16x_{4}&=&6 \end{array}\right .$

2. Determine the value of $k$ so that the following system of linear equations has a solution.
$$\begin{array}{l} \left\{\begin{array}{rrr} x+2y+3z&=&7\\ 3x+2y+5z&=&9\\ 5x+2y+7z&=&k \end{array}\right . \end{array}$$

3. Determine whether the following matrix is regular. If so, find the inverse matrix, (a) $\left(\begin{array}{rrr} 2&3&4\\ 1&2&3\\ -1&1&4 \end{array}\right)$

(b) $\left(\begin{array}{rrrr} 0&0&0&1\\ 0&0&1&0\\ 0&1&0&0\\ 1&0&0&0 \end{array}\right)$

4. Determine the value $a$ so that the following matrix is regular.

$\left(\begin{array}{rrr} 2&0&-3\\ 1&-1&a\\ 5&3&4 \end{array}\right)$

5. Show that the following matrix is regular, and show the following matrix as a product of elementary matrices. $A = \left(\begin{array}{rrr} 2&-1&0\\ 4&3&2\\ 3&0&1 \end{array}\right)$.

6. Suppose that all entries of one row of the square matrix are 0. The show that $A$ is not regular.

7. Suppose that $A,B$ are regular matrices of the order $n$. Then show thatthe product of $AB$ is also regular and satisfies

$$(AB)^{-1} = B^{-1}A^{-1}$$