11.5 Solving matrices

On the existence of solutions

Remark

A homogeneous system \(AX = 0\) always has a solution: \(X = 0\). This is called the trivial solution.

A non-homogeneous system \(AX = b \neq 0\) may have no solution.

Example

\(\begin{cases} x + y = 1 \\ -x - y = 0 \end{cases}\) No solution.

Theorem

Let \(A\in M_{m\times n}\left(\mathbb{F}\right)\). The homogeneous system \(AX = 0\) has a non-trivial solution if and only if the row-reduced echelon form of \(A\) has \(r\) pivots with \(r \neq n\).

Proof. \(r \leq n\) (because pivots are in different columns).

Assume \(r = n\). Then \(A\sim\) ​\(\Rightarrow x_{n}=0,x_{n-1}=0,\dots,x_1=0\Rightarrow X=0\).

Assume \(r < n\). Then \(A\sim\)​​\(\Rightarrow\exists\;i_0\) such that the column \(i_0\) has no pivot.

Now, set \(x_{i_0} = t\) and all the other variables corresponding to non-pivot columns to \(0\).

Then clear the variables corresponding to the pivots.

Example

\(\begin{pmatrix}1 & 2 & 0 & 0\\ 0 & 0 & 1 & 3\end{pmatrix}\begin{pmatrix}x_1\\ x_2\\ x_3\\ x_4\end{pmatrix}=\begin{pmatrix}0\\ 0\end{pmatrix}\)​

Let \(\begin{cases} x_2 = t \\ x_4 = 0 \end{cases}\), then \(\begin{cases}x_1+2t=0\\ x_3=0\end{cases}\)

Proof:

\(r \leq n\)

Assume \(r = n\) ...

Assume \(r < n\). Let \(i_1<\dots<i_{r}\) be the columns corresponding to the pivots. Let \(j_1<\dots<j_{n-r}\) be the columns with no pivots.

Now, set \(x_{j_1} = t\), \(x_{j_2} = \dots = x_{j_{n-r}} = 0\). The other variables \(x_{i_1}, \dots, x_{i_r}\) are now uniquely determined. (Because the \(k_{th}\) equation has variables \(x_{i_l}\) and \(x_{j_1}, \dots, x_{j_{n-r}}\))

Only 1 pivot variable.

Corollary

Let \(A \in M_{m \times n} (\mathbb{F})\). For the homogeneous system \(AX = 0\), it holds:

(a) If \(m < n\), it has non-trivial solutions, like this\(\begin{pmatrix} *&*&*&*&*\\*&*&*&*&*\\*&*&*&*&*\end{pmatrix}\)

Assume \(m<n\). Since pivots must be in different rows, then \(r\leq m\), and hence \(r<n\). Theorem implies that \(AX=0\) has a non-trivial solution.

(b) If \(m = n\), it has only the trivial solution if and only if the row-reduced echelon form of \(A\) is the identity matrix \(I\).

Assume \(m=n\). Recall the \(AX=0\) is equivalent to \(RX=0\) (R is the row-reduced echelon form). If \(R\) is the identity, then \(RX=X\), and hence the system \(RX=0\) has only the trivial solution. If \(R\) is not the identity, then \(r<n\) and Theorem implies that there is a non-trivial solution for \(RX=0\).

Theorem

Let \(A \in M_{m \times n} (\mathbb{F})\), \(b \in M_{m \times 1} (\mathbb{F})\). Let \((A | b)\) be the augmented matrix corresponding to the non-homogeneous system \(AX = b\) and let \((B|b^{\prime})\) be the augmented matrix where \(B\) is the row-reduced echelon form of \(A\) and \((B | b')\) is obtained from \((A | b)\) by row operations. Then, \(AX = b\) has a solution if and only if the zero rows of \(B\) correspond to zero values of \(b'\).

\(\text{Proof:}\)

\(A|b\xrightarrow{\text{row-eq}}B|b^{\prime}=\)​

(where \(r = \text{number of pivots}\))

Hence, if \(b_j' \neq 0\) for some \(j = r + 1, \dots, m\), then equation \(j\) has no solution.

If \(b_{r+1}' = \dots = b_m' = 0\), the system is equivalent to which has a solution

Why? We can set the non-pivot be \(0\), others be corresponding \(b\). Then we must can get a solution.

Example

\(A = \begin{pmatrix} 1 & 1 \\ 1 & 2 \\ 1 & -1 \end{pmatrix}\), \(b_1 = \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix}\), \(b_2 = \begin{pmatrix} 0 \\ 1 \\ -2 \end{pmatrix}\)

\(\begin{pmatrix} 1 & 1 & | & 0 & | & 0 \\ 1 & 2 & | & 1 & | & 1 \\ 1 & -1 & | & 1 & | & -2 \end{pmatrix} \sim \begin{pmatrix} 1 & 1 & | & 0 & | & 0 \\ 0 & 1 & | & 1 & | & 1 \\ 0 & -2 & | & 1 & | & -2 \end{pmatrix} \sim \begin{pmatrix} 1 & 0 & | & -1 & | & -1 \\ 0 & 1 & | & 1 & | & 1 \\ 0 & 0 & | & 3 & | & 0 \end{pmatrix}\)

\(\Rightarrow AX = 0\) has only the trivial solution: \(W = \{ 0 \}\).

\(\Rightarrow AX = b_1\) has \(\text{NO SOLUTION}\).

\(\Rightarrow AX = b_2\) has a solution \(X_0 = \begin{pmatrix} -1 \\ 1 \end{pmatrix}\), and all the solutions are \(X_0 + W\). So that \(X_0 = \begin{pmatrix} -1 \\ 1 \end{pmatrix}\) is the \(\text{unique solution}\).

Notation

The rank of a matrix \(A \in M_{m \times n} (\mathbb{F})\) is the number of pivots of its row-reduced echelon form.

Invertible matrices and inverses (in \(M_{n \times n} (\mathbb{F})\))

A left inverse of \(A\) is a \(B\) such that \(BA = I\).

A right inverse of \(A\) is a \(C\) such that \(AC = I\).

A two-sided inverse is a \(B\) such that \(BA = I = AB\). In this case, we say that \(A\) is invertible, and \(B\) is its inverse. Since it is unique, \(B = A^{-1}\).

Remark

If \(A\) has a left inverse \(B\) and a right inverse \(C\), then \(B = C\).

Proof

\(B = B \cdot I = B (AC) = (BA) C = I \cdot C = C\)

\((A^{-1})^{-1} = A, \quad (AB)^{-1} = B^{-1}A^{-1}\)

Elementary matrices

An elementary matrix is a matrix obtained from the identity matrix \(I\) by a single row operation.

Examples

• Type 1: \(\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \rightarrow \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & \pi \end{pmatrix}\)
• Type 2: \(\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \rightarrow \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}\)
• Type 3: \(\begin{pmatrix}1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1\end{pmatrix}\rightarrow\begin{pmatrix}1 & 0 & 0\\ 0 & 1 & -2\\ 0 & 0 & 1\end{pmatrix}\)

Notation

If the operation is called \(e\), then the corresponding elementary matrix is \(A = e(I)\).

Remark

Given matrices \(A\) and \(B\) obtained from \(A\) by a single row operation \(e\), we have \(B = e(I) A\).

Type 1:\(\begin{pmatrix}a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ \lambda a_{i1} & \lambda a_{i2} & \cdots & \lambda a_{in}\\ \vdots & \vdots & \ddots & \vdots\\ a_{m1} & a_{m2} & \cdots & a_{mn}\end{pmatrix}=\begin{pmatrix}1 & 0 & 0 & 0 & 0 & 0\\ 0 & \ddots & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & \lambda & 0 & 0\\ 0 & 0 & 0 & 0 & \ddots & 0\\ 0 & 0 & 0 & 0 & 0 & 1\end{pmatrix}\begin{pmatrix}a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{i1} & a_{i2} & \cdots & a_{in}\\ \vdots & \vdots & \ddots & \vdots\\ a_{m1} & a_{m2} & \cdots & a_{mn}\end{pmatrix}\)

Type 2: \(\begin{pmatrix}a_{11} & a_{12} & \cdots & a_{1n}\\ a_{j1} & a_{j2} & \cdots & a_{jn}\\ \vdots & \vdots & \ddots & \vdots\\ a_{i1} & a_{i2} & \cdots & a_{in}\\ \vdots & \vdots & \ddots & \vdots\\ a_{m1} & a_{m2} & \cdots & a_{mn}\end{pmatrix}=\begin{pmatrix}1 & 0 & \cdots & 0 & \cdots & 0\\ 0 & \ddots & & \vdots & & \vdots\\ \vdots & & 0 & \cdots & 1 & \vdots\\ 0 & \cdots & 1 & \cdots & 0 & 0\\ \vdots & & \vdots & & \ddots & \vdots\\ 0 & \cdots & 0 & \cdots & 0 & 1\end{pmatrix}\begin{pmatrix}a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{m1} & a_{m2} & \cdots & a_{mn}\end{pmatrix}\)​

Type 3: \(\begin{pmatrix}a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{i1}+\lambda a_{j1} & a_{i2}+\lambda a_{j2} & \cdots & a_{in}+\lambda a_{jn}\\ \vdots & \vdots & \ddots & \vdots\\ a_{m1} & a_{m2} & \cdots & a_{mn}\end{pmatrix}=\begin{pmatrix}1 & 0 & \cdots & 0 & \cdots & 0\\ 0 & \ddots & & \vdots & & \vdots\\ \vdots & & 1 & \lambda & & \vdots\\ 0 & \cdots & 0 & 1 & \cdots & 0\\ \vdots & & \vdots & & \ddots & \vdots\\ 0 & \cdots & 0 & 0 & \cdots & 1\end{pmatrix}\begin{pmatrix}a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{i1} & a_{i2} & \cdots & a_{in}\\ \vdots & \vdots & \ddots & \vdots\\ a_{m1} & a_{m2} & \cdots & a_{mn}\end{pmatrix}\)

Theorem

Elementary matrices are invertible.

Lemma

A square row-reduced echelon matrix is invertible if and only if it is the identity matrix.

Proof.

Assume \(A \neq I\), hence it has a zero row (the last one). In particular, \(AX = 0\) has a non-trivial solution.

That is, there exists \(X_0 \neq 0\) such that \(AX_0 = 0\).

Since \(A\) is invertible, \(A^{-1}(AX_0)=A^{-1}\cdot0=0\Rightarrow I\cdot X_0=0\Rightarrow X_0=0\) (associativity)

This is a contradiction.

Theorem

The following are equivalent (for \(A \in M_{n \times n}(\mathbb{F})\)):

(a) \(A\) is invertible.

(b) \(A\) is row-equivalent to the identity matrix \(I\).

(c) \(A\) is the product of elementary matrices.

Proof

(a) \(\Rightarrow\) (b): Let \(R\) be the row-reduced echelon form of \(A\). Then \(R = E_k \cdots E_1 A\).

Since \(A\) is invertible and so are \(E_1, \dots, E_k\), it follows that \(R\) is invertible. By Lemma, \(R = I\).

(b) \(\Rightarrow\) (c): \(I=R=E_{k}\cdots E_1A\Rightarrow E_1^{-1}\cdots E_{k}^{-1}=A\).

(c) \(\Rightarrow\) (a): \(\checkmark\)

Corollary

If \(A\) is invertible and \(E_k \cdots E_1 A = I\), then \(A^{-1} = E_k \cdots E_1\).

So that \(A^{-1} = e_{k}(e_{k-1}(\cdots e_{2}(e_{1}(I)) \cdots ))\).

Theorem

Let \(A \in M_{n \times n}(\mathbb{F})\). The following are equivalent:

(a) \(A\) is invertible.

(b) The equation \(AX = 0\) has only the trivial solution.

(c) The equation \(AX = Y \neq 0\) has a unique solution.

Proof: Let \(R\) be the row-reduced echelon form of \(A\).

• We have (a) if and only if \(R = I\).
• (b) if and only if \(R = I\).
• (c) if and only if \(R = I\).

Corollary

If \(A\) has a left or right inverse, then it is invertible.

Proof:

• If \(BA = I\Rightarrow BAX=IX\Rightarrow B0=IX\Rightarrow X=0\), then \(AX = 0\) has only the trivial solution. Hence, \(A\) is invertible.
• If \(AC = I\), then \(C\) is a left inverse, implying \(C\) is invertible, which in turn implies \(A = C^{-1}\) is invertible.

Corollary

\(A = A_1 A_2 \dots A_k\) is invertible if and only if \(A_i\) is invertible for all \(i = 1, \dots, k\).

Example

\(A = \begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix}\)

Row operations to transform \(A\) to \(I\):

\(\begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix} \xrightarrow{} \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \xrightarrow{} \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = I\)

Applying the same row operations to \(I\) to find \(A^{-1}\):

\(I = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \xrightarrow{} \begin{pmatrix} 1 & 0 \\ -1 & 1 \end{pmatrix} \xrightarrow{} \begin{pmatrix} 2 & -1 \\ -1 & 1 \end{pmatrix} = A^{-1}\)

‍

‍