An n × m matrix A is both a list of rows, acting as linear functions on 𝔽m, and a list of columns, representing vectors in 𝔽m. Accordingly, we can interpret matrix/vector multiplication in dual ways: As a transformation of the input vector, or as a linear combination of the matrix columns.

Solving Systems of Linear Equations

While Mathematica has a dedicated command LinearSolve[A,b] for solving vector equation Ax = b, we summarized information we obtained so far from two previous sections (Gaussian elimination and Gauss--Jordan elimination).

A linear system of m equations in n unknowns x1, x2, ... , xn is expressed as

\[ \begin{split} 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, \\ \quad\vdots \qquad &\ \vdots \\ a_{m1}\,x_1 + a_{m2}\,x_2 + \cdots + a_{mn}\,x_n &= b_m . \end {split} \]
The coefficient matrix and the right hand side are
\[ {\bf A} = \begin{bmatrix} a_{11} & a_{12} & a_{13} & \cdots & a_{1n} \\ a_{21} & a_{22} & a_{23} & \cdots & a_{2n} \\ \vdots& \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & a_{m3} & \cdots & a_{mn} \end{bmatrix} \qquad\mbox{and} \qquad {\bf b} = \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{pmatrix} , \]
respectively. The unknown vector x can also be written in column form. Then the above system could be written in a compact form Ax = b. A solution to the the linear system of equations is an n-tuple < s1, s2, ... , sn > of complex or real numbers that satisfies the vector equation As = b. The set of all solutions to the system Ax = b is called the solution set of the system.

A linear system Ax = b is called homogeneous provided the right side b = 0. Every homogeneous linear system can be represented as a vector equation Ax = 0.
A linear system Ax = b is called nonhomogeneous (or inhomogeneous) provided that b0. For a given nonhomogeneous linear system of equations Ax = b, the linear system Ax = 0 is called associated homogeneous system.
A homogeneous linear equation Ax = 0 always has an obvious solution x = 0; we call 0 the trivial solution. We will learn in the next chapter that some homogeneous linear systems have solutions other than the trivial solution; such solutions are called nontrivial.

Corollary: If m < n, the system Ax = 0 has a nonzero solution.

Example: Consider the system of algebraic equations
\begin{align*} x_1 + 2\,x_2 - x_3 &= 0 , \\ 2\,x_1 + 2\,x_2 - 3\, x_3 &= 0 . \end{align*}
Let
\[ {\bf A} = \begin{bmatrix} 1&2&-1 \\ 2&1 & -2 \end{bmatrix} \]
be the coefficient matrix of this system. With Mathematica, it is easy to find nontrivial solutions of the system Ax = 0:
NullSpace[{{1, 2, -1}, {2, 1, -2}}]
{{4, -1, 2}}
So any vector that is proportional to [ 4, -1, 2 ] is a solution to the given homogeneous system of linear equations. ■
If A is an m×n matrix, the general solution of the linear system Ax = b is the sum of a particular solution of the system Ax = b and a linear combination c1 v1 + c2 v2 + ⋯ + ck vk of solutions v1, v2, ... , vk of the homogeneous system Av = 0.
The following theorem is the main statement about solvability of the nonhomogeneous system of equation. It will be proved later in part 3.

Theorem: Let A be an m×n matrix and b be an m-vector. The the linear vector equation Ax = b has a solution if and only if b is orthogonal to every solution y (so its dot product by =0 is zero) of the homogeneous equation A*y = 0, where A* is the n×m matrix obtained from A by transposition and taking complex conjugate. Recall that A* is called the adjoint matrix to A.

Theorem: Let A be an m×n matrix.

  • (Overdetermined Case) If mn, then the linear system Ax = b is consistent for at least one vector b in ℝm.
  • (Underdetermined Case) If mn, then for each vector b in ℝm the linear system Ax = b is either inconsistent or has infinitely many solutions.
Suppose that a matrix A is transformed/equivalent to the row echelon matrix B by elementary row operations. This means that every nonzero row in matrix B has a leading entry, which is the leftmost nonzero entry in a nonzero row and all entries below it are zeroes. A pivot position in a matrix A is a location in A that corresponds to a leading term in B, the echelon form of A. A pivot column is a column of A that contains a pivot position.

Theorem: An m×n linear system Ax = b in variables x1, x2, ... , xn is consistent (that is, it has a solution) for all b∈ℝm if and only if the reduced echelon form of A has m pivots.

For the linear system Ax = b, let the augmented matrix [A|b] is transformed to the row echelon form B. If the last column of B is a pivot column, then the system is inconsistent since B contains a row of the form
\[ \left[ 0 \ 0 \ \cdots \ 0 \ * \right] , \]
where * is a nonzero number. This corresponds to the contradictory equation 0ċxn = *. Hence the number of pivot columns of the augmented matrix cannot exceed the number of pivot columns of A, if the system is to be sonsistent. Moreover, the number of pivot columns of A cannot exceed the number of rows of A because no two pivots of a matrix can occur in teh same row.

Suppose, therefore, that the reduced row echelon form (we use the reduced form instead of the echelon form for simplicity because it does not matter) B of the augmented matrix has m pivots. Then the m-th row of B is of the form

\[ \left[ 0 \ 0 \ \ldots \ 0 \ 1\ b_{m,j+1} \ \cdots \ b_{m, n+1} \right] . \]
This row corresponds to the equation
\[ x_j + b_{m,j+1} x_{j+1} + \cdots + b_{m,n} = b_{m,n+1} . \]
In that case, we can assign values to the variables xj+1, xj+2, ... , xn, solve for xm, and use back substitution to build a solution b∈ℝm for the system. This clearly works for any assignment of values to the variables xi. On the otehr hand, if the number of pivots of B is less than m, then B contains a row of the form
\[ \left[ b_{i,n} \ b_{i,n} \ \cdots \ b_{in} \ 1\ b_{i(n+1)} \right] = \left[ 0 \ 0 \ \cdots \ 0 \ b_{i(n+1)} \right]. \]
If we let b = [ b1, ... , bi, ... , bm ] be any vector in ℝm, in which \( b_i = b_{i(n+1)} \ne 0, \) the system Ax = b is inconsistent. Hence, there exists a vector b∈ℝm that is not a solution of Ax = b. This proves the theorem.
Example: Consider the linear system of equations
\[ \begin{split} x_1 -2\,x_2 -3\,x_3 + 2\, x_4 &= 3, \\ 2\,x_1 + 2\,x_2 - x_3 &= -2, \\ 2\,x_1 - x_2 + 2\,x_3 + 3\, x_4 &= 16, \\ x_1 + 3\,x_2 + 3\,x_3 - x_4 &= 1 . \end {split} \]
The corresponding augmented matrix is equivalent to row echelon form:
\[ \left[ {\bf A} \,|\,{\bf b} \right] = \begin{bmatrix} \color{red}{\bf 1}&-2&-3&2&3 \\ 2&\color{red}{\bf 2}&-1&0&-2 \\ 2&-1&\color{red}{\bf 2}&3&16 \\ 1&3&3&-1&1 \end{bmatrix} \, \sim \, \begin{bmatrix} 1&-2&-3&2&3 \\ 0&6&5&-4&-8 \\ 0&3&8&-1&10 \\ 0&5&6&-3&-2 \end{bmatrix} \, \sim \, \begin{bmatrix} \color{red}{\bf 1}&-2&-3&2&3 \\ 0&\color{red}{\bf 6}&5&-4&-8 \\ 0&0&\color{red}{\bf 11} & 2 & 28 \\ 0&0&0&0&0 \end{bmatrix} . \]
Since matrix A has only 3 pivots (marked bold font), the given system has a solution not for arbitrary input vector b. One solution can be identified to be p = [1,-1,2,3], but the general solution, according to Mathematica
NullSpace[{{1, -2, -3, 2}, {2, 2, -1, 0}, {2, -1, 2, 3}, {1, 3, 3, -1}}]
{{-10, 9, -2, 11}}
depends on one parameter:
\[ {\bf x} = [1,-1,2,3] + t\,[-10, 9, -2, 11] , \qquad t \in \mathbb{R} \]
because the solution set of the associated homogeneous equation Ax = 0 is spanned on the vector [-10, 9, -2, 11] . On the other hand, if try to solve the same system of linear equations for another input vector b = [1,-1,2,2], we will be in bad luck---there is no solution. Indeed, Mathematica provides the reduced row echelon form:
RowReduce[{{1, -2, -3, 2, 3}, {2, 2, -1, 0, -2}, {2, -1, 2, 3, 1}, {1, 3, 3, -1, 1}}]
{{1, 0, 0, 10/11, 0}, {0, 1, 0, -(9/11), 0}, {0, 0, 1, 2/11, 0}, {0, 0, 0, 0, 1}}
Therefore, we transform the given augmented matrix to the following one (with three pivots)
\[ \left[ {\bf A} \,|\,{\bf b}\right] = \begin{bmatrix} \color{red}{\bf 1}&-2&-3&2&3 \\ 2&\color{red}{\bf 2}&-1&0&-2 \\ 2&-1&\color{red}{\bf 2}&3&1 \\ 1&3&3&-1&\color{red}{\bf 1} \end{bmatrix} \, \sim \, \begin{bmatrix} \color{red}{\bf 1}&0&0&\frac{10}{11}&0 \\ 0&\color{red}{\bf 1}&0&-\frac{9}{11}&0 \\ 0&0&\color{red}{\bf 1}&\frac{2}{11} &0 \\ 0&0&0&0&\color{red}{\bf 1} \end{bmatrix} \]
that has no solution because the last equation 0x4 = 1 provides the contradiction. ■

Example: Consider the system of four linear equations
\[ \begin{split} x_1 -2\,x_2 -3\,x_3 + 2\, x_4 &= 3, \\ 2\,x_1 + 2\,x_2 - x_3 + x_4 &= -2, \\ 2\,x_1 - x_2 + 2\,x_3 + 3\, x_4 &= 1, \\ x_1 + 3\,x_2 + 3\,x_3 - x_4 &= 1 . \end {split} \]
Its augmented matrix is transformed to the equivalent reduced row echelon form:
\[ \left[ {\bf A} \,|\,{\bf b}\right] = \begin{bmatrix} \color{red}{\bf 1}&-2&-3&2&3 \\ 2&\color{red}{\bf 2}&-1&1&-2 \\ 2&-1&\color{red}{\bf 2}&3&1 \\ 1&3&3&\color{red}{\bf -1}&1 \end{bmatrix} \, \sim \, \begin{bmatrix} \color{red}{\bf 1}&0&0&0&\frac{17}{2} \\ 0&\color{red}{\bf 1}&0&0&-\frac{11}{2} \\ 0&0&\color{red}{\bf 1} & 0 & \frac{1}{2} \\ 0&0&0&\color{red}{\bf 1}&-\frac{15}{2} \end{bmatrix} . \]
Mathematica confirms
RowReduce[{{1, -2, -3, 2, 3}, {2, 2, -1, 1, -2}, {2, -1, 2, 3, 1}, {1, 3, 3, -1, 1}}]
{{1, 0, 0, 0, 17/2}, {0, 1, 0, 0, -(11/2)}, {0, 0, 1, 0, 1/2}, {0, 0, 0, 1, -(15/2)}}