Chapter 2 Rectangular Systems and Echelon Forms

2.1 Row Echelon Form and Rank

Modified Gaussian Elimination

Suppose that $\mathbf{U}$ is the augmented matrix associated with the system after $i − 1$ elimination steps have been completed. To execute the $i^{th}$ step, proceed as follows:

• Moving from left to right in $\mathbf{U}$, locate the first column that contains a nonzero entry on or below the $i^{th}$ position — say it is $\mathbf{U}_{*j}$.
• The pivotal position for the $i^{th}$ step is the $(i, j)$ -position.
• If necessary, interchange the $i^{th}$ row with a lower row to bring a nonzero number into the $(i, j)$ -position, and then annihilate all entries below this pivot.
• If row $\mathbf{U}{i*}$ as well as all rows in $\mathbf{U}$ below $\mathbf{U}{i*}$ consist entirely of zeros, then the elimination process is completed.

Row Echelon Form

An $m \times n$ matrix $\mathbf{E}$ with rows $\mathbf{E}{i*}$ and columns $\mathbf{E}{*j}$ is said to be in row echelon form provided the following two conditions hold.

• If Ei∗ consists entirely of zeros, then all rows below $\mathbf{E}_{i*}$ are also entirely zero; i.e., all zero rows are at the bottom.
• If the first nonzero entry in $\mathbf{E}{i*}$ lies in the $j^{th}$ position, then all entries below the ith position in columns $\mathbf{E}{1}$, $\mathbf{E}_{2}$, … , $\mathbf{E}_{*j}$ are zero.

Rank of a Matrix

The entries in $\mathbf{E}$ are not uniquely determined by $\mathbf{A}$.Nevertheless, it can be proven that the “form” of $\mathbf{E}$ is unique in the sense that the positions of the pivots in $\mathbf{E}$ are uniquely determined by the entries in $\mathbf{A}$.

Suppose $\mathbf{A}_{m \times n}$ is reduced by row operations to an echelon form $\mathbf{E}$.The rank of $\mathbf{A}$ is defined to be the number

\[\begin{align*} rank (\mathbf{A}) &= \text{number of pivots} \\ &= \text{number of nonzero rows in} \;\mathbf{E} \\ &= \text{number of basic columns in} \;\mathbf{A}, \end{align*}\]

where the basic columns of $\mathbf{A}$ are defined to be those columns in $\mathbf{A}$ that contain the pivotal positions.

Pay particular attention to the fact that the basic columns are extracted from $\mathbf{A}$ and not from the row echelon form $\mathbf{E}$.

2.2 Reduced Row Echelon Form

A matrix $\mathbf{E}_{m \times n}$ is said to be in reduced row echelon form provided that the following three conditions hold.

• $\mathbf{E}$ is in row echelon form.

• The first nonzero entry in each row (i.e., each pivot) is 1.

• All entries above each pivot are 0.

If $\mathbf{A}$ is transformed by row operations to a reduced row echelon form $\mathbf{E}{\mathbf{A}}$, then both the “form” as well as the individual entries in $\mathbf{E}{\mathbf{A}}$ are uniquely determined by $\mathbf{A}$. In other words, the reduced row echelon form $\mathbf{E}_{\mathbf{A}}$ produced from $\mathbf{A}$ is independent of whatever elimination scheme is used.

$\mathbf{E}_{\mathbf{A}}$ Notation

For a matrix ${\mathbf{A}}$, the symbol $\mathbf{E}_{\mathbf{A}}$ will hereafter denote the unique reduced row echelon form derived from ${\mathbf{A}}$ by means of row operations.

Column Relationships in $\mathbf{A}$ and $\mathbf{E}_{\mathbf{A}}$

• Each nonbasic column $\mathbf{E}{*k}$ in EA is a combination (a sum of multiples) of the basic columns in $\mathbf{E}{\mathbf{A}}$ to the left of $\mathbf{E}_{*k}$. That is,

\[\begin{align*} \mathbf{E}_{*k} &= \mu_1 \mathbf{E}_{*b_1} + \mu_2 \mathbf{E}_{*b_2} + \dots + \mu_j \mathbf{E}_{*b_j}\\ &= \mu_1 \begin{pmatrix} 1 \\ 0 \\ \vdots \\ 0 \\ \vdots \\ 0 \end{pmatrix} + \mu_2 \begin{pmatrix} 0 \\ 1 \\ \vdots \\ 0 \\ \vdots \\ 0 \end{pmatrix} + \dots + \mu_j \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 1 \\ \vdots \\ 0 \end{pmatrix} = \begin{pmatrix} \mu_1 \\ \mu_2 \\ \vdots \\ \mu_j \\ \vdots \\ 0 \end{pmatrix}, \end{align*}\]

where the $\mathbf{E}{*b_i}$’s are the basic columns to the left of $\mathbf{E}{k}$ and where the multipliers $\mu_i$ are the first $j$ entries in $\mathbf{E}_{k}$.

• The relationships that exist among the columns of $\mathbf{A}$ are exactly the same as the relationships that exist among the columns of $\mathbf{E}{\mathbf{A}}$. In particular, if $\mathbf{A}{*k}$ is a nonbasic column in $\mathbf{A}$, then

\[\begin{align*} \mathbf{A}_{*k} &= \mu_1 \mathbf{A}_{*b_1} + \mu_2 \mathbf{A}_{*b_2} + \dots + \mu_j \mathbf{A}_{*b_j}, \end{align*}\]

where the $\mathbf{A}{*b_i}$’s are the basic columns to the left of $\mathbf{A}{k}$ and where the multipliers $\mu_i$ are the first $j$ entries in $\mathbf{E}_{k}$.

In summary, the utility of $\mathbf{E}_{\mathbf{A}}$ lies in its ability to reveal dependencies in data stored as columns in an array $\mathbf{A}$. The nonbasic columns in $\mathbf{A}$ represent redundant information in the sense that this information can always be expressed in terms of the data contained in the basic columns.

2.3 Consistency of Linear Systems

A system of $m$ linear equations in $n$ unknowns is said to be a consistent system if it possesses at least one solution. If there are no solutions, then the system is called inconsistent.

Consistency

Each of the following is equivalent to saying that $\left[\mathbf{A} \vert \mathbf{b} \right]$ is consistent.

• In row reducing $\left[\mathbf{A} \vert \mathbf{b} \right]$, a row of the following form never appears: \(\left(0 \quad 0 \quad \dots \quad 0 \quad \vert \quad \alpha \right), \text{where} \alpha \neq 0.\)

• $\mathbf{b}$ is a nonbasic column in $\left[\mathbf{A} \vert \mathbf{b} \right]$.

• $ rank\left[ \mathbf{A} \vert \mathbf{b} \right] = rank (\mathbf{A}) $.

• $\mathbf{b}$ is a combination of the basic columns in $\mathbf{A}$.

2.4 Homogeneous Systems

A system of $m$ linear equations in $n$ unknowns

\[\begin{equation*} \begin{aligned} a_{11}x_1 \; + \; a_{12}x_2 \; + \; \dots \; + \; a_{1n}x_n \; &= \; 0, \\ a_{21}x_1 \; + \; a_{22}x_2 \; + \; \dots \; + \; a_{2n}x_n \; &= \; 0, \\ \vdots \\ a_{m1}x_1 \; + \; a_{m2}x_2 \; + \; \dots \; + \; a_{mn}x_n \; &= \; 0, \end{aligned} \end{equation*}\]

in which the right-hand side consists entirely of 0’s is said to be a homogeneous system. If there is at least one nonzero number on the right-hand side, then the system is called nonhomogeneous.

The solution consisting of all zeros is referred to as the trivial solution.

Summary

Let $\mathbf{A}_{m \times n}$ be the coefficient matrix for a homogeneous system of $m$ linear equations in $n$ unknowns, and suppose $rank(\mathbf{A}) = r$.

• The unknowns that correspond to the positions of the basic columns (i.e., the pivotal positions) are called the basic variables, and the unknowns corresponding to the positions of the nonbasic columns are called the free variables.

• There are exactly $r$ basic variables and $n − r$ free variables.

• To describe all solutions, reduce $\mathbf{A}$ to a row echelon form using Gaussian elimination, and then use back substitution to solve for the basic variables in terms of the free variables. This produces the general solution that has the form \(x = x_{f_1} \mathbf{h_1} + x_{f_2} \mathbf{h_2} + \dots + x_{f_{n-r}} \mathbf{h_{n-r}} ,\) where the terms $x_{f_1} , x_{f_2} , \dots , x_{f_{n-r}}$ are the free variables and where $\mathbf{h_1}, \mathbf{h_2}, \dots , \mathbf{h_{n-r}}$ are $n \times 1$ columns that represent particular solutions of the homogeneous system. The $\mathbf{h_1}$’s are independent of which row echelon form is used in the back substitution process. As the free variables $x_{f_i}$ range over all possible values, the general solution generates all possible solutions.

• A homogeneous system possesses a unique solution (the trivial solution) if and only if $rank(\mathbf{A}) = n$ — i.e., if and only if there are no free variables.

2.5 Nonhomogeneous Systems

\[\begin{equation*} \begin{aligned} a_{11}x_1 \; + \; a_{12}x_2 \; + \; \dots \; + \; a_{1n}x_n \; &= \; b_1, \\ a_{21}x_1 \; + \; a_{22}x_2 \; + \; \dots \; + \; a_{2n}x_n \; &= \; b_2, \\ \vdots \\ a_{m1}x_1 \; + \; a_{m2}x_2 \; + \; \dots \; + \; a_{mn}x_n \; &= \; b_m, \end{aligned} \end{equation*}\]

is said to be nonhomogeneous whenever $b_i \neq 0$ for at least one $i$.

Summary

Let $\left[\mathbf{A} \vert \mathbf{b} \right]$ be the augmented matrix for a consistent $m \times n$ nonhomogeneous system in which $rank(\mathbf{A}) = r$.

• Reducing $\left[\mathbf{A} \vert \mathbf{b} \right]$ to a row echelon form using Gaussian elimination and then solving for the basic variables in terms of the free variables leads to the general solution \(x = \mathbf{p} + x_{f_1} \mathbf{h_1} + x_{f_2} \mathbf{h_2} + \dots + x_{f_{n-r}} \mathbf{h_{n-r}}.\) As the free variables $x_{f_i}$ range over all possible values, this general solution generates all possible solutions of the system.

• Column $\mathbf{p}$ is a particular solution of the nonhomogeneous system.

• The expression $x_{f_1} \mathbf{h_1} + x_{f_2} \mathbf{h_2} + \dots + x_{f_{n-r}} \mathbf{h_{n-r}}$ is the general solution of the associated homogeneous system.

• Column $\mathbf{p}$ as well as the columns $\mathbf{h_i}$ are independent of the row echelon form to which $\left[\mathbf{A} \vert \mathbf{b} \right]$ is reduced.

• The system possesses a unique solution if and only if any of the following is true.

  • $rank(\mathbf{A}) = r = n =$ number of unknowns.
  • There are no free variables.
  • The associated homogeneous system possesses only the trivial solution.

---

• Previous
  矩阵分析与应用（一）
• Next
  矩阵分析与应用（三）

---