9 Solving the matrix equation \({A} \vec{x} = \vec{0}\)

9.1 Vector spaces

Before proceeding, let’s define a key mathematical structure: the vector space. A vector space is a set of vectors that is closed under linear operations—meaning that any linear combination of vectors in the set is also in the set. This is called a “space” because it generalizes the idea of a geometric space filled with points. While we focus here on tuples of numbers and their geometric interpretation, the concept of vector spaces is much broader and includes, for example, spaces of functions¹. The formal definition of a vector space is based on eight axioms:

Definition 9.1 (Vector space) A vector space is a set \(V\) of objects called vectors. Suppose \(\vec{u}\), \(\vec{v}\), and \(\vec{w}\) are elements of \(V\), and \(a\) and \(b\) are scalars. Then:

\(\vec{u}+(\vec{v}+\vec{w})=(\vec{u}+\vec{v})+\vec{w}\) (associativity of addition)
\(\vec{u}+\vec{v}=\vec{v}+\vec{u}\) (commutativity of addition)
\(V\) contains an element \(\vec{0}\), called the zero vector, such that for all \(\vec{v}\) in \(V\): \(\vec{v}+\vec{0}=\vec{v}\)
For every \(\vec{v}\) in \(V\) there exists an element \(-\vec{v}\) in \(V\) such that \(\vec{v} + (-\vec{v})=\vec{0}\) (additive inverse)
For every \(\vec{v}\) in \(V\): \(1\vec{v}=\vec{v}\)
For every \(\vec{v}\) in \(V\): \((ab)\vec{v}=a(b\vec{v})\) (compatibility of scalar multiplication)
For every \(\vec{u}\), \(\vec{v}\) in \(V\): \(b(\vec{u}+\vec{v})=b\vec{u} + b\vec{v}\) (distributivity over vector addition)
For every \(\vec{v}\) in \(V\): \((a+b)\vec{v}=a\vec{v} + b\vec{v}\) (distributivity over scalar addition)

Although not stated explicitly, if \(\vec{u}\) and \(\vec{v}\) are in \(V\), then so is \(\vec{u} + \vec{v}\). Similarly, \(a\vec{u}\) is in \(V\) for any scalar \(a\). These two properties together mean that any linear combination \(a\vec{u} + b\vec{v}\) is also in the vector space. This is called the closure property. The most important rules to remember are:

A vector space must contain a \(\vec{0}\) element and be closed under linear combinations of its elements.

For column vectors of length \(n\), the \(\vec{0}\) element is simply the column vector of all zeros:

\[ \vec{0} = \begin{bmatrix} 0 \\ 0 \\ \vdots \\ 0 \end{bmatrix} \]

With our definition of vector addition:

\[ \vec{v} + \vec{0} = \begin{bmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{bmatrix} + \begin{bmatrix} 0 \\ 0 \\ \vdots \\ 0 \end{bmatrix} = \begin{bmatrix} v_1 + 0 \\ v_2 + 0 \\ \vdots \\ v_n + 0 \end{bmatrix} = \vec{v} \]

as required by rule 3.

The concept of vector spaces is important because solution sets of systems of linear equations can be described as vector spaces, where column vectors represent the solutions. We will see that solution sets to linear equations are either a vector space, or the sum of a vector space and a particular vector. In defining these solution sets, we also encounter the concept of a vector subspace. A vector subspace \(V'\) is a subset of a vector space \(V\) that is itself a vector space. In particular, a subspace must contain the zero vector and be closed under linear combinations. We can illustrate these concepts geometrically.

Example 9.1 (Subspace of the two-dimensional plane) The two-dimensional plane (or \(\mathbb{R}^2\)) is a vector space: it contains the zero vector (the origin \((0,0)\)), and the sum of any two 2-tuples is again in the plane. A proper vector subspace of the plane is a line through the origin. Such a line contains the origin and is closed under linear combinations. Since there are infinitely many lines through the origin, there are infinitely many subspaces of \(\mathbb{R}^2\). Note that such a line cannot be written as \(\mathbb{R}^1\) because its elements are still 2-tuples \((x, y)\), with \(x\) and \(y\) related (e.g., \(y = 2x\)).

Name two reasons why a line not going through the origin does not correspond to a vector subspace.

Answer

The line does not contain the zero vector.
Not every linear combination of vectors on the line remains on the line.

In three dimensions (\(\mathbb{R}^3\)), subspaces can be the origin, lines through the origin, or planes through the origin. In higher dimensions (\(\mathbb{R}^n\)), subspaces are higher-dimensional slices, but all must contain the origin.

9.2 Homogeneous systems of linear equations

Consider a system of \(m\) linear equations in \(n\) variables:

\[ \begin{alignedat}{8} a_{11} x_1 & {}+{} & a_{12} x_2 & {}+{} & \cdots & {}+{} & a_{1n} x_n &= 0 \\ a_{21} x_1 & {}+{} & a_{22} x_2 & {}+{} & \cdots & {}+{} & a_{2n} x_n &= 0 \\ \vdots & & & & \vdots & & & \vdots \\ a_{m1} x_1 & {}+{} & a_{m2} x_2 & {}+{} & \cdots & {}+{} & a_{mn} x_n &= 0 \end{alignedat} \]

Such systems, with zeros on the right-hand side, are called homogeneous systems. This can be written as the matrix equation \(\mat{A}\vec{x} = \vec{0}\), where \(\vec{0}\) is the zero vector of length \(m\). We will show that the solution set of such a system forms a vector space—usually a subspace of \(\mathbb{R}^n\). First, the zero vector is always a solution: setting all variables to zero satisfies the equations. Second, any linear combination of solutions is also a solution.

Theorem 9.1 If \(\vec{u}\) and \(\vec{v}\) are solutions of \(\mat{A}\vec{x}=\vec{0}\), then \(a\vec{u} + b\vec{v}\) is also a solution for any real \(a\) and \(b\).

Proof. If \(\vec{u}\) and \(\vec{v}\) are solutions, then \(\mat{A}\vec{u} = \vec{0}\) and \(\mat{A}\vec{v} = \vec{0}\). Consider \(a\vec{u} + b\vec{v}\):

\[ \begin{aligned} \mat{A} (a\vec{u} + b\vec{v}) &= \mat{A} a \vec{u} + \mat{A} b \vec{v} = a \mat{A} \vec{u} + b \mat{A} \vec{v} = a \vec{0} + b \vec{0} \\ &= \vec{0} + \vec{0} = \vec{0} \end{aligned} \]

Thus, the solution set to a homogeneous system is a vector space, but to describe it explicitly, we use Gaussian elimination.

Example 9.2 Consider the system:

\[ \begin{alignedat}{6} u & {}+{} & v & {}+{} & w &= 0 \\ u & {}+{} & 2v & {}+{} & 3w &= 0 \\ & & v & {}+{} & 2w &= 0 \end{alignedat} \]

or, as a matrix equation:

\[ \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \\ 0 & 1 & 2 \end{bmatrix} \begin{bmatrix} u \\ v \\ w \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} \]

We solve this system using Gaussian elimination. Since the right-hand side is all zeros, we can ignore it during elimination:

\[ \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \\ 0 & 1 & 2 \end{bmatrix} \yields \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 2 \\ 0 & 1 & 2 \end{bmatrix} \yields \begin{bmatrix} \textcolor{red}{1} & 1 & 1 \\ 0 & \textcolor{red}{1} & 2 \\ 0 & 0 & 0 \end{bmatrix} \]

There are two pivots; with three variables, the solution will involve one free variable. The reduced system is:

\[ \begin{alignedat}{6} \textcolor{red}{u} & {}+{} & \textcolor{red}{v} & {}+{} & w &= 0 \\ & & \textcolor{red}{v} & {}+{} & 2w &= 0 \\ {} & {} & {} & {} & 0 &= 0 \end{alignedat} \]

We can choose any variable as free, but systematically, we continue to reduced row-echelon form (Gauss-Jordan elimination):

\[ \begin{bmatrix} \textcolor{red}{1} & 1 & 1 \\ 0 & \textcolor{red}{1} & 2 \\ 0 & 0 & 0 \end{bmatrix} \yields \begin{bmatrix} \textcolor{red}{1} & 0 & -1 \\ 0 & \textcolor{red}{1} & 2 \\ 0 & 0 & 0 \end{bmatrix} \]

This gives:

\[ \begin{alignedat}{2} \textcolor{red}{u} &= w \\ \textcolor{red}{v} &= -2w \end{alignedat} \]

So the solution set is \(\{(u,v,w)\mid w \in \mathbb{R}, u=w, v=-2w\}\), or as a vector space:

\[ \begin{bmatrix} u \\ v \\ w \end{bmatrix} = \begin{bmatrix} w \\ -2w \\ w \end{bmatrix} = \begin{bmatrix} 1\\ -2\\ 1 \end{bmatrix} w \tag{9.1}\]

Or, in set notation:

\[ \left\{ \begin{bmatrix} 1\\ -2\\ 1 \end{bmatrix} w \;\Biggr\rvert\; w \in \mathbb{R} \right\} \] The zero vector is included (take \(w=0\)), and any linear combination of solutions is again a solution. Geometrically, this is a line through the origin in 3D space.

In the next example, two free variables are needed.

Example 9.3 Consider the homogeneous matrix equation:

\[ \begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & 2 & 3 & 4\\ 0 & 1 & 2 & 3 \end{bmatrix} \begin{bmatrix} u \\ v \\ w \\ x \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} \]

Without performing Gaussian elimination, what can you say about the number of free variables?

Answer

There must be at least one free variable, since there are more variables than equations.

Performing Gauss-Jordan elimination:

\[ \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 2 & 3 & 4\\ 0 & 1 & 2 & 3 \end{bmatrix} \yields \begin{bmatrix} 1 & 1 & 1 & 1\\ 0 & 1 & 2 & 3\\ 0 & 1 & 2 & 3 \end{bmatrix} \yields \begin{bmatrix} \textcolor{red}{1} & 1 & 1 & 1\\ 0 & \textcolor{red}{1} & 2 & 3 \\ 0 & 0 & 0 & 0 \end{bmatrix} \yields \begin{bmatrix} \textcolor{red}{1} & 0 & -1 & -2 \\ 0 & \textcolor{red}{1} & 2 & 3 \\ 0 & 0 & 0 & 0 \end{bmatrix} \] which is equivalent to:

\[ \begin{alignedat}{2} \textcolor{red}{u} &= w + 2 x\\ \textcolor{red}{v} &= -2w - 3 x \end{alignedat} \] So the solution set is:

\[ \left\{ \begin{bmatrix} 1 \\ -2\\ 1 \\ 0 \end{bmatrix} w + \begin{bmatrix} 2 \\ -3\\ 0 \\ 1 \end{bmatrix} x \;\Biggr\rvert\; w \in \mathbb{R} \, \text{,} \, x \in \mathbb{R} \right\} \]

9.3 Some terminology

Rank and null space of a matrix

Some useful linear algebra terminology:

Rank of a matrix: The rank of a matrix \(\mat{A}\), written \(\rank{\mat{A}}\), is the number of pivot variables after Gaussian or Gauss-Jordan elimination. If \(\mat{A}\) has \(n\) columns and \(m\) rows, it is full row-rank if \(\rank{\mat{A}}=m\) and full column-rank if \(\rank{\mat{A}}=n\).
Null space of a matrix: The solution set to \(\mat{A} \vec{x} = \vec{0}\) is always a vector space, called the null space or kernel of \(\mat{A}\), written \(\nul{\mat{A}}\) or \(\ker(\mat{A})\). The null space will be important when solving non-homogeneous equations \(\mat{A} \vec{x} = \vec{b}\).

In Example 9.2, the matrix \(\mat{A}=\Bigl[\begin{smallmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \\ 0 & 1 & 2 \end{smallmatrix}\Bigr]\) has \(\rank{\mat{A}} = 2\) and \(\nul{\mat{A}}=\ker(\mat{A})=\Bigl[\begin{smallmatrix*}[r] 1 \\ -2 \\ 1 \end{smallmatrix*}\Bigr] w\) with \(w \in \mathbb{R}\). Remember, \(\nul{\mat{A}}\) is a set of vectors (a vector space), while \(\rank{\mat{A}}\) is an integer.

What was the rank of the matrix in Example 9.3?

Span and dimension

Given vectors \(\{\vec{v}_1, \vec{v}_2, \ldots, \vec{v}_n\}\), the span of this set is the vector space of all linear combinations:

\[ \left\{ c_1 \vec{v}_1 + c_2 \vec{v}_2 + \ldots + c_n \vec{v}_n \;\rvert\; c_1, c_2, \ldots, c_n \in \mathbb{R}\right\} \]

We say this set of vectors spans the vector space. In examples 9.2 and 9.3, we wrote the null spaces as spans of 1 or 2 vectors.

The dimension of a vector space is the minimal number of vectors needed to span it. For the null space, \(\dim(\nul{\mat{A}})\) is called the nullity of the matrix. It equals the number of free variables needed to describe the null space. The number of columns in a matrix equals the total number of variables, which is the sum of the number of pivots (rank) and the number of free variables (nullity). This leads to the rank-nullity theorem:

Theorem 9.2 (Rank-nullity theorem) The sum of the rank and nullity of a matrix equals its number of columns \(n\): \[ \rank{\mat{A}} + \dim(\nul{\mat{A}}) = n \]

Proof. This is equivalent to:

\[ \begin{align*} n & = \#\textrm{columns} \\ & = \textrm{total } \#\textrm{variables} \\ & = \#\textrm{non-free variables} + \#\textrm{free variables} \\ & = \#\textrm{pivots} + \#\textrm{free variables} \\ & = \rank{\mat{A}} + \dim(\nul{\mat{A}}) \end{align*} \]

9.4 Basis of a vector space

A basis of a vector space \(V\) is a minimal set of vectors \(\vec{v_1}, \vec{v_2}, \ldots, \vec{v_n}\) such that every \(\vec{w} \in V\) can be written as a linear combination \(c_1 \vec{v_1} + c_2 \vec{v_2} + \cdots + c_n \vec{v_n}\). That is, \(V\) cannot be described by fewer than \(n\) vectors. This basis spans \(V\).

A basis is not unique. For example, two different bases for \(\mathbb{R}^2\) are \(\bigl\{\bigl[\begin{smallmatrix} 1 \\ 0 \end{smallmatrix}\bigr], \bigl[\begin{smallmatrix} 0 \\ 1 \end{smallmatrix}\bigr] \bigr\}\) and \(\bigl\{\bigl[\begin{smallmatrix} 1 \\ 1 \end{smallmatrix}\bigr], \bigl[\begin{smallmatrix} 2 \\ 1 \end{smallmatrix}\bigr] \bigr\}\). There are infinitely many bases for a vector space.

It is also possible to span a vector space with more vectors than in a basis. For example, \(\mathbb{R}^2\) is also spanned by \(\bigl\{\bigl[\begin{smallmatrix} 1 \\ 0 \end{smallmatrix}\bigr], \bigl[\begin{smallmatrix} 0 \\ 1 \end{smallmatrix}\bigr], \bigl[\begin{smallmatrix} 1 \\ 1 \end{smallmatrix}\bigr] \bigr\}\), but this set is not a basis. For \(\mathbb{R}^n\), a basis always has \(n\) vectors.

Later, we will define independence of vectors and see that the vectors in a basis are pairwise independent. When performing Gaussian elimination, the vectors describing the null space are independent and thus form a basis.

9.5 Exercises

Vector space

Exercise 22.

How many proper vector subspaces are there of the vector space consisting of the vector space \(\mathbb{R}^1\)?

Null space

Exercise 23.

a. Work out the multiplication \(\mat{A} \vec{x}\) below to find out whether \((2,1,1)\) is a solution vector to the system \(\mat{A} \vec{x} = \vec{0}\). \[ \mat{A} \vec{x} = \begin{bmatrix} 3 & -6 & 0 \\ 0 & 2 & -2 \\ 1 & -1 & -1 \end{bmatrix} \begin{bmatrix}2 \\ 1 \\ 1\end{bmatrix} \]

b. Can you find more solutions to \(\mat{A} \vec{x} = \vec{0}\)?

Exercise 24.

Using the reduced row-echelon form, calculate the null space of the following matrix \[ \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 4 \\ 2 & 4 & 8 \end{bmatrix} \]

Exercise 25.

Using the reduced row-echelon form, calculate the null space of the following matrix \[ \begin{bmatrix} 1 & 2 & 1 \\ 2 & 6 & 3 \\ 0 & 2 & 5 \end{bmatrix} \]

Exercise 26.

Calculate the nullspace of

\[\begin{equation*} \begin{bmatrix} 1 & 2 & -1 & 1 \\ 2 & 4 & -3 & 2 \\ -1 & -2 & 1 & -1 \end{bmatrix} \end{equation*}\]

Exercise 27.

Calculate the nullspace of

\[\begin{equation*} \begin{bmatrix} 1 & 2 & -1 & 3 \\ 2 & 4 & -2 & 6 \\ 3 & 6 & -3 & 9 \end{bmatrix} \end{equation*}\]

Exercise 28.

a. Without any elimination, what can you already say about the number of free variables? \[ \mat{A} = \begin{bmatrix} 1 & 2 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 2 & 0 & 1 \end{bmatrix} \]

b. Reduce the matrix to echelon form to find its rank. Which variables are free? Find the complete solution set to \(\mat{A} \vec{x} = \vec{0}\).

Exercise 29.

Reduce the following matrix to echelon form to find its rank. Which variables are free? Find the complete solution set to \(\mat{B} \vec{x} = \vec{0}\). \[ \mat{B} = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} \]

Exercise 30.

What can you say about the nullspace of a full column rank matrix

when it is a square matrix?
when it is a non-square matrix?

Application

Exercise 31.

Consider the metabolic network shown in Figure 9.1 A.

Figure 9.1: Simplified metabolic cell model (A) Graphic representation of the fluxes. The double arrow to P means that two P are produced per G. (B) Three elementary flux modes of this network.

a. Write down the stoichiometry matrix for the fluxes \(v_0\), \(v_1\), \(v_2\), \(v_3\), \(v_4\) and \(v_{BM}\) and the intracellular metabolites \(G\), \(P\), ADP and ATP.

b. Solve the steady state equation of the matrix and give a description of the nullspace.

c. Elementary flux Modes (EFMs) are vectors spanning the steady state solution space (see Figure 9.1 B). Show that the elementary flux modes

\[ \text{EFM1} = \begin{bmatrix} 5 \\ 5 \\ 0 \\ 9 \\ 0 \\ 1 \end{bmatrix}, \quad \text{EFM2} = \begin{bmatrix} 50 \\ 50 \\ 99 \\ 0 \\ 0 \\ 1 \end{bmatrix},\quad \text{EFM3} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 10 \\ 11 \\ 1 \end{bmatrix} \\ \] are in the nullspace.

d. Do the EFMs form a basis of the nullspace?

This may sound abstract, but it simply means that linear combinations of functions are also functions. Such spaces are important, for example, in studying solutions to systems of differential equations. The linear algebra methods we discuss here also apply to those cases.↩︎