Elementary Matrix Operations and Systems of Linear Equations

Elementary matrix operations and elementary matrices

Let $A$ be an $m \times n$ matrix. Any one of the following three operations on the rows [columns] of $A$ is called an elementary row [column] operation:

1. interchanging any two rows [columns] of $A$;

2. multiplying any row [column] of $A$ by a nonzero scalar;

3. adding any scalar multiple of a row [column] of $A$ to another row [column].

An $n \times n$ elementary matrix is a matrix obtained by performing an elementary operation on $I_n$. The elementary matrix is said to be of type 1, 2, or 3 according to whether the elementary operation performed on $I_n$ is a type 1, 2, or 3 operation, respectively.

Theorems

1. Let $A \in M_{m \times n}(F)$, and suppose that $B$ is obtained from $A$ by performing an elementary row [column] operation. Then there exists an $m \times m$ [$n \times n$] elementary matrix $E$ such that $B = EA$ [$B = AE$]. In fact, $E$ is obtained from $I_m$ [$I_n$] by performing the same elementary row [column] operation as that which was performed on $A$ to obtain $B$.

2. Elementary matrices are invertible, and the inverse of an elementary matrix is an elementary matrix of the same type.

The rank of a matrix and matrix inverses

If $A \in M_{m \times n}(F)$, we define the rank of $A$, denoted $\operatorname{rank}(A)$, to be the rank of the linear transformation $L_{A} : F^{n} \to F^{m}$.

Let $A$ and $B$ be $m \times n$ and $m \times p$ matrices, respectively. By the augmented matrix $(A \mid B)$, we mean the $m \times (n + p)$ matrix $(A\ B)$, that is, the matrix whose first $n$ columns are the columns of $A$, and whose last $p$ columns are the columns of $B$.

Theorems

1. Let $T : V \to W$ be a linear transformation between finite-dimensional vector spaces, and let $\beta$ and $\gamma$ be ordered bases for $V$ and $W$, respectively. Then

$$\begin{equation*} \operatorname{rank}(T) = \operatorname{rank}([T]_{\beta}^{\gamma}). \end{equation*}$$

2. Let $A$ be an $m \times n$ matrix. If $P$ and $Q$ are invertible $m \times m$ and $n \times n$ matrices, respectively, then

   (a) $\operatorname{rank}(AQ) = \operatorname{rank}(A)$,

   (b) $\operatorname{rank}(PA) = \operatorname{rank}(A)$, and therefore,

   (c) $\operatorname{rank}(PAQ) = \operatorname{rank}(A)$.

3. The rank of any matrix equals the maximum number of its linearly independent columns; that is, the rank of a matrix is the dimension of the subspace generated by its columns.

4. Let $A$ be an $m \times n$ matrix of rank $r$. Then $r \le m$, $r \le n$, and, by means of a finite number of elementary row and column operations, $A$ can be transformed into the matrix

   $$\begin{equation*} D = \begin{pmatrix} I_r & O_1 \\ O_2 & O_3 \end{pmatrix}, \end{equation*}$$

   where $O_1$, $O_2$, and $O_3$ are zero matrices. Thus $D_{ii} = 1$ for $i \le r$ and $D_{ij} = 0$ otherwise.

5. Let $A$ be an $m \times n$ matrix of rank $r$. Then there exist invertible matrices $B$ and $C$ of sizes $m \times m$ and $n \times n$, respectively, such that $D = BAC$, where

$$\begin{equation*} D = \begin{pmatrix} I_r & O_1 \\ O_2 & O_3 \end{pmatrix}, \end{equation*}$$

​ is the $m \times n$ matrix in which $O_1$, $O_2$, and $O_3$ are zero matrices.

6. (a) $\operatorname{rank}(A^{t}) = \operatorname{rank}(A)$.

   (b) The rank of any matrix equals the maximum number of its linearly independent rows; that is, the rank of a matrix is the dimension of the subspace generated by its rows.

   (c) The rows and columns of any matrix generate subspaces of the same dimension, numerically equal to the rank of the matrix.

7. (a) $\operatorname{rank}(UT) \le \operatorname{rank}(U)$.

   (b) $\operatorname{rank}(UT) \le \operatorname{rank}(T)$.

   (c) $\operatorname{rank}(AB) \le \operatorname{rank}(A)$.

   (d) $\operatorname{rank}(AB) \le \operatorname{rank}(B)$.

Systems of linear equations

$$\begin{equation*} \begin{aligned} a_{11}x_{1} + a_{12}x_{2} + \cdots + a_{1n}x_{n} &= b_{1} \\ a_{21}x_{1} + a_{22}x_{2} + \cdots + a_{2n}x_{n} &= b_{2} \\ & \ \vdots \\ a_{m1}x_{1} + a_{m2}x_{2} + \cdots + a_{mn}x_{n} &= b_{m}, \end{aligned} \end{equation*}$$

where $a_{ij}$ and $b_{i}$ ($1 \le i \le m$ and $1 \le j \le n$) are scalars in a field $F$ and $x_{1}, x_{2}, \ldots, x_{n}$ are $n$ variables taking values in $F$, is called a system of $m$ linear equations in $n$ unknowns over the field $F$.

The $m \times n$ matrix

$$\begin{equation*} A = \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} \end{equation*}$$

is called the coefficient matrix of the system $(S)$.

If we let

$$\begin{equation*} x = \begin{pmatrix} x_{1} \\ x_{2} \\ \vdots \\ x_{n} \end{pmatrix} \qquad\text{and}\qquad b = \begin{pmatrix} b_{1} \\ b_{2} \\ \vdots \\ b_{m} \end{pmatrix}, \end{equation*}$$

then the system $(S)$ may be rewritten as a single matrix equation

$$\begin{equation*} Ax = b. \end{equation*}$$

To exploit the results that we have developed, we often consider a system of linear equations as a single matrix equation. A solution to the system $(S)$ is an $n$-tuple

$$\begin{equation*} s = \begin{pmatrix} s_{1} \\ s_{2} \\ \vdots \\ s_{n} \end{pmatrix} \in F^{n} \end{equation*}$$

such that $As = b$. The set of all solutions to the system $(S)$ is called the solution set of the system. System $(S)$ is called consistent if its solution set is nonempty; otherwise it is called inconsistent.

A system $Ax = b$ of $m$ linear equations in $n$ unknowns is said to be homogeneous if $b = 0$. Otherwise the system is said to be nonhomogeneous.

Any homogeneous system has at least one solution, namely, the zero vector.

Theorems

1. Let $K$ be the solution set of a system of linear equations $Ax = b$, and let $K_{H}$ be the solution set of the corresponding homogeneous system $Ax = 0$. Then for any solution $s$ to $Ax = b$, $$\begin{equation*} K = \{s\} + K_{H} = \{\, s + k : k \in K_{H} \,\}. \end{equation*}$$

​

2. Let $Ax = 0$ be a homogeneous system of $m$ linear equations in $n$ unknowns over a field $F$. Let $K$ denote the set of all solutions to $Ax = 0$. Then

   $$\begin{equation*} K = N(L_A), \end{equation*}$$

   hence $K$ is a subspace of $F^n$ of dimension

   $$\begin{equation*} n - \mathrm{rank}(L_A) = n - \mathrm{rank}(A). \end{equation*}$$

3. Let $Ax = b$ be a system of $n$ linear equations in $n$ unknowns. If $A$ is invertible, then the system has exactly one solution, namely $A^{-1}b$. Conversely, if the system has exactly one solution, then $A$ is invertible.

4. Let $Ax = b$ be a system of linear equations. Then the system is consistent if and only if

   $$\begin{equation*} \mathrm{rank}(A) = \mathrm{rank}(A|b). \end{equation*}$$

Gaussian elimination

A matrix is said to be in reduced row echelon form if the following three conditions are satisfied:

(a) Any row containing a nonzero entry precedes any row in which all the entries are zero (if any).

(b) The first nonzero entry in each row is the only nonzero entry in its column.

(c) The first nonzero entry in each row is $1$ and it occurs in a column to the right of the first nonzero entry in the preceding row.

The reduced row echelon form of a matrix is unique.

Let $Ax = b$ be a system of $r$ nonzero equations in $n$ unknowns. Suppose that $\operatorname{rank}(A) = \operatorname{rank}(A|b)$ and that $(A|b)$ is in reduced row echelon form. Then

(a) $\operatorname{rank}(A) = r$.

(b) If the general solution obtained by the procedure above is of the form

$$\begin{equation*} s = s_0 + t_1 u_1 + t_2 u_2 + \cdots + t_{\,n-r}\,u_{\,n-r}, \end{equation*}$$

then $\{u_1, u_2, \ldots, u_{\,n-r}\}$ is a basis for the solution set of the corresponding homogeneous system, and $s_0$ is a solution to the original system.

LU decomposition

Let $A$ be an $m \times n$ matrix. Suppose that $A$ admits an LU decomposition of the form

$$\begin{equation*} A = LU, \end{equation*}$$

where

• $L$ is an $m \times m$ lower triangular matrix with $1$'s on the diagonal, and
• $U$ is an $m \times n$ upper triangular matrix.

We consider the system

$$\begin{equation*} Ax = b. \end{equation*}$$

Because $A = LU$, the system becomes

$$\begin{equation*} LUx = b. \end{equation*}$$

Let

$$\begin{equation*} y = Ux. \end{equation*}$$

Then the solution process consists of the following two steps.