4 Applications of Gaussian elimination

4.1 Gaussian elimination

In the Algorithmics module M01 you learned how to use Gaussian elimination to solve a system of equations of the form \[\tag{4.1} \mathbf{A}\vec{x}=\vec{b}\] for some given matrix \(\mathbf{A}\in M_{m,n}(\mathbb{K}),\) vector \(\vec{b} \in \mathbb{K}^m\) and unknown \(\vec{x} \in \mathbb{K}^n.\) Many concrete problems in Linear Algebra lead to systems of the form (4.1). A few sample problems that can be solved with Gaussian elimination are discussed below.

Solving equation of the type (4.1) hinges on the elementary observation that a vector \(\vec{x} \in \mathbb{K}^n\) solves \(\mathbf{A}\vec{x}=\vec{b}\) if and only if it solves \(\mathbf{B}\mathbf{A}\vec{x}=\mathbf{B}\vec{b},\) where \(\mathbf{B}\in M_{m,m}(\mathbb{K})\) is any invertible \(m\)-by-\(m\) matrix.

In the Gaussian elimination algorithm, the matrix \(\mathbf{B}\) is chosen among three types of matrices:

As an exercise in matrix multiplication, we compute the effect of left multiplication with elementary matrices.

For \(\mathbf{A}=(A_{ij})_{1\leqslant i,j\leqslant m} \in M_{m,n}(\mathbb{K}),\) we obtain \[\left[\mathbf{L}_{k,l}(s)\mathbf{A}\right]_{ij}=\sum_{r=1}^m\left(\delta_{ir}+s\delta_{ik}\delta_{lr}\right)A_{rj}=A_{ij}+s\delta_{ik}A_{lj}=\left\{\begin{array}{cc} A_{ij}+sA_{lj} & i=k \\ A_{ij} & i\neq k \end{array}\right.,\] where we use that \([\mathbf{1}_{m}]_{ir}=\delta_{ir}\) and \([\mathbf{E}_{k,l}]_{ir}=\delta_{ik}\delta_{lr}.\) Therefore, multiplying the matrix \(\mathbf{A}\) with \(\mathbf{L}_{k,l}(s)\) from the left, adds \(s\) times the \(l\)-th row of \(\mathbf{A}\) to the \(k\)-th row of \(\mathbf{A}\) and leaves \(\mathbf{A}\) unchanged otherwise.

Likewise, we obtain \[\left[\mathbf{D}_k(s)\mathbf{A}\right]_{ij}=\sum_{r=1}^m\left(\delta_{ir}+(s-1)\delta_{ik}\delta_{kr}\right)A_{rj}=\left\{\begin{array}{cc} sA_{ij} & i=k \\ A_{ij} & i\neq k \end{array}\right..\] Therefore, multiplying the matrix \(\mathbf{A}\) with \(\mathbf{D}_{k}(s)\) from the left, multiplies the \(k\)-th row of \(\mathbf{A}\) with \(s\) and leaves \(\mathbf{A}\) unchanged otherwise.

Finally, \[\begin{aligned} \left[\mathbf{P}_{k,l}\mathbf{A}\right]_{ij}&=\sum_{r=1}^m(\delta_{ir}-\delta_{ik}\delta_{kr}-\delta_{il}\delta_{lr}+\delta_{ik}\delta_{lr}+\delta_{il}\delta_{rk})A_{rj}\\ &=A_{ij}-\delta_{ik}A_{kj}-\delta_{il}A_{lj}+\delta_{ik}A_{lj}+\delta_{il}A_{kj}\\ &=A_{ij}+\delta_{ik}\left(A_{lj}-A_{kj}\right)+\delta_{il}\left(A_{kj}-A_{lj}\right)=\left\{\begin{array}{cc}A_{lj} & i=k \\ A_{kj} & i=l \\ A_{ij} & i\neq k, i\neq l \end{array}\right.. \end{aligned}\] Therefore, multiplying the matrix \(\mathbf{A}\) with \(\mathbf{P}_{k,l}\) from the left, swaps the \(k\)-th row of \(\mathbf{A}\) with the \(l\)-th row of \(\mathbf{A}\) and leaves \(\mathbf{A}\) unchanged otherwise.

These calculations immediately imply:

The sceptical reader may also verify this fact by direct computation with the help of the following lemma:

For each row in a matrix, if the row does not consist of zeros only, then the leftmost nonzero entry is called the leading coefficient of that row.

Gaussian elimination from the Algorithmics module M01 implies the following statement:

4.2 Applications

4.2.1 Compute the inverse of a matrix

An algorithm using Gaussian elimination for computing the inverse of an invertible matrix relies on the following fact:

Suppose the matrix \(\mathbf{A}\in M_{n,n}(\mathbb{K})\) is invertible. Applying Gauss–Jordan elimination to \(\mathbf{A},\) we cannot encounter a zero row, since the occurrence of a zero row corresponds to a non-trivial linear combination of row vectors which gives the zero vector. This is excluded by the above proposition. Having no zero row vectors, the Gauss–Jordan elimination applied to \(\mathbf{A}\) must give the identity matrix \(\mathbf{1}_{n}.\) Thus we can find a sequence of elementary matrices \(\mathbf{B}_1,\ldots,\mathbf{B}_N,\) \(N \in \mathbb{N},\) so that \[\mathbf{1}_{n}=\mathbf{B}_N\mathbf{B}_{N-1}\cdots \mathbf{B}_2\mathbf{B}_1\mathbf{A}.\] In other words, \(\mathbf{B}_N\mathbf{B}_{N-1}\cdots \mathbf{B}_2\mathbf{B}_1\) is the inverse of \(\mathbf{A}.\) This gives the following recipe for computing the inverse of \(\mathbf{A}\):

We write the matrix \(\mathbf{A}\) and \(\mathbf{1}_{n}\) next to each other, say \(\mathbf{A}\) on the left and \(\mathbf{1}_{n}\) on the right. We then perform Gauss–Jordan elimination on \(\mathbf{A}.\) At each step, we also perform the Gauss–Jordan elimination step to the matrix on the right. Once Gauss–Jordan elimination terminates, we thus obtain \(\mathbf{B}_N\mathbf{B}_{N-1}\cdots \mathbf{B}_2\mathbf{B}_1\mathbf{A}\) on the left and \(\mathbf{B}_N\mathbf{B}_{N-1}\cdots \mathbf{B}_2\mathbf{B}_1\mathbf{1}_{n}\) on the right. But since \(\mathbf{B}_N\mathbf{B}_{N-1}\cdots \mathbf{B}_2\mathbf{B}_1\mathbf{1}_{n}=\mathbf{B}_N\mathbf{B}_{N-1}\cdots \mathbf{B}_2\mathbf{B}_1\) (notice the absence of \(\mathbf{1}_{n}\) after the equality sign), the right hand side is the inverse of \(\mathbf{A}.\)

4.2.2 Compute a basis of a subspace

Gaussian elimination can also be used to compute a basis for a vector subspace \(U\) of a finite dimensional \(\mathbb{K}\)-vector space \(V.\) We assume that \(U=\operatorname{span}\{v_1,\ldots,v_k\}\) for some vectors \(v_i \in V,\) \(1\leqslant i\leqslant k.\) We assume that \(\dim U\geqslant 1\) so that not all vectors are the zero vector.

We first consider the special case where \(V\) is the space \(\mathbb{K}_n\) of row vectors of length \(n\) and with entries in \(\mathbb{K}.\) Recall that we denote the row vectors by small Greek letters. We write \(\mathbb{K}_n^m\) for the \(m\)-fold Cartesian product \((\mathbb{K}_n)^m\) of \(\mathbb{K}_n.\) Clearly, we have a bijective mapping \[\Omega : \mathbb{K}_n^m \to M_{m,n}(\mathbb{K}), \quad (\vec{\nu}_1,\ldots,\vec{\nu}_m) \mapsto \begin{pmatrix} \vec{\nu}_1 \\ \vdots \\ \vec{\nu}_m\end{pmatrix}\] which simply writes the row vectors \((\vec{\nu}_1,\ldots,\vec{\nu}_m)\) into a matrix with the \(k\)-th row vector from the \(m\)-tuple of row vectors becoming the \(k\)-th row of the matrix.

We have \[\begin{aligned} \mathbf{L}_{k,l}(s)\Omega(\vec{\nu}_1,\ldots,\vec{\nu}_m)&=\Omega\left(\vec{\nu}_1,\ldots,\vec{\nu}_{k-1},\vec{\nu}_k+s\vec{\nu}_l,\vec{\nu}_{k+1},\ldots,\vec{\nu}_m\right),\\ \mathbf{D}_{k}(s)\Omega(\vec{\nu}_1,\ldots,\vec{\nu}_m)&=\Omega\left(\vec{\nu}_1,\ldots,\vec{\nu}_{k-1},s\vec{\nu}_k,\vec{\nu}_{k+1},\ldots,\vec{\nu}_m\right),\\ \mathbf{P}_{k,l}\Omega(\vec{\nu}_1,\ldots,\vec{\nu}_m)&=\Omega\left(\vec{\nu}_1,\ldots,\vec{\nu}_{k-1},\vec{\nu}_l,\vec{\nu}_{k+1},\ldots,\vec{\nu}_{l-1},\vec{\nu}_k,\vec{\nu}_{l+1},\ldots,\vec{\nu}_m\right). \end{aligned}\] Notice that all these operations do not change the span of the vectors \(\vec{\nu}_1,\ldots,\vec{\nu}_m.\) More precisely, if \((\vec{\nu}_1,\ldots,\vec{\nu}_m)\) is an \(n\)-tuple of row vectors and if \(\Omega\left(\vec{\omega}_1,\ldots,\vec{\omega}_m\right)=\mathbf{B}\Omega (\vec{\nu}_1,\ldots,\vec{\nu}_m)\) for some elementary matrix \(\mathbf{B},\) then \[\operatorname{span}\{\vec{\nu}_1,\ldots,\vec{\nu}_m\}=\operatorname{span}\{\vec{\omega}_1,\ldots,\vec{\omega}_m\}.\] Applying Gaussian elimination to the matrix \(\Omega(\vec{\nu}_1,\ldots,\vec{\nu}_m)\) gives a list of elementary matrices \(\mathbf{B}_1,\ldots,\mathbf{B}_N\) such that \[\mathbf{B}_N\mathbf{B}_{N-1}\cdots \mathbf{B}_2\mathbf{B}_1\Omega(\vec{\nu}_1,\ldots,\vec{\nu}_m)=\Omega(\vec{\omega}_1,\ldots,\vec{\omega}_{r},0_{\mathbb{K}_n},\dots,0_{\mathbb{K}_n})\] where \(1\leqslant r\leqslant m\) and \(0_{\mathbb{K}_n}\) denotes the zero vector in \(\mathbb{K}_n.\) By construction, the matrix \(\mathbf{A}=\Omega(\vec{\omega}_1,\ldots,\vec{\omega}_{r},0_{\mathbb{K}_n},\dots,0_{\mathbb{K}_n})\) is REF. Since the leading coefficient of \(\vec{\omega}_i\) is always strictly to the right of the leading coefficient of \(\vec{\omega}_{i-1},\) it follows that the vectors \(\vec{\omega}_1,\ldots,\vec{\omega}_{r}\) are linearly independent. Therefore, a basis of \(\operatorname{span}\{\vec{\nu}_1,\ldots,\vec{\nu}_m\}\) is given by \(\{\vec{\omega}_1,\ldots,\vec{\omega}_{r}\}.\)

The general case can be treated with the help of the following facts:

We now describe a recipe to treat the general case of a subset \(U=\operatorname{span}\{v_1,\ldots,v_m\}\) of a finite dimensional \(\mathbb{K}\)-vector space \(V\):

1. Fix an isomorphism \(\Phi : V \to \mathbb{K}_n\) and write \(\vec{\nu}_i=\Phi(v_i)\) for \(1\leqslant i\leqslant m.\)

2. Apply Gaussian elimination to the matrix \(\Omega(\vec{\nu}_1,\ldots,\vec{\nu}_m)\) to obtain a set of new vectors \((\vec{\omega}_1,\ldots,\vec{\omega}_{r},0_{\mathbb{K}_n},\ldots,0_{\mathbb{K}_n})\) for some \(r \in \mathbb{N}.\)

3. Apply the inverse isomorphism \(\Phi^{-1}\) to the obtained list of vectors. This gives the desired basis \(\{\Phi^{-1}(\vec{\omega}_1),\ldots,\Phi^{-1}(\vec{\omega}_{r})\}\) of \(U.\)

4.2.3 Compute the image and rank of a linear map

Let \(V,W\) be finite dimensional \(\mathbb{K}\)-vector spaces and \(f : V \to W\) a linear map. By computing the image of a linear map \(f,\) we mean computing a basis of \(\operatorname{Im}(f).\)

In order to compute a basis for \(\operatorname{Im}(f)\) we use the following lemma:

Knowing that \(\operatorname{Im}(f)=\operatorname{span}\{f(v_1),\ldots,f(v_n)\}\) we can apply the recipe from Section 4.2.2 to \(U=\operatorname{span}\{f(v_1),\ldots,f(v_n)\}.\) By definition, the number of basis vectors for \(\operatorname{Im}(f)\) is the rank of \(f.\)

4.2.4 Compute the kernel and nullity of a linear map

In order to find a recipe for computing the kernel and nullity of a linear map, we first start with a related problem. Let \(\mathbf{A}\in M_{n,m}(\mathbb{K})\) be an \(n\times m\)-matrix and \[U=\left\{\vec{\xi} \in \mathbb{K}_n \,|\,\vec{\xi} \mathbf{A}=0_{\mathbb{K}_m}\right\},\] where \(\vec{\xi} \mathbf{A}\) is defined via matrix multiplication of the row vector \(\vec{\xi} \in \mathbb{K}_n=M_{1,n}(\mathbb{K})\) and the matrix \(\mathbf{A}\in M_{n,m}(\mathbb{K}).\) Notice that \(0_{\mathbb{K}_n} \in U\) and if \(\vec{\xi}_1,\vec{\xi}_2 \in U,\) then \(s_1\vec{\xi}_1+s_2\vec{\xi}_2 \in U\) for all \(s_1,s_2 \in \mathbb{K}.\) By Definition 3.21

Definition 3.21 • Vector subspace ➔

Let \(V\) be a \(\mathbb{K}\)-vector space. A subset \(U\subset V\) is called a vector subspace of \(V\) if \(U\) is non-empty and if \[\tag{3.8} s_1\cdot_Vv_1+_Vs_2\cdot_V v_2 \in U\quad \text{for all}\; s_1,s_2 \in \mathbb{K}\; \text{and all}\; v_1,v_2 \in U.\]

, it follows that \(U\) is a vector subspace of \(\mathbb{K}_{n}.\) We want to compute a basis for \(U.\) Applying Gauss elimination to the matrix \(\mathbf{A},\) we obtain \(r \in \mathbb{N}\) and elementary matrices \(\mathbf{B}_1,\ldots,\mathbf{B}_N\) so that \[\mathbf{B}_N\cdots \mathbf{B}_1\mathbf{A}=\Omega\left(\vec{\omega}_1,\ldots,\vec{\omega}_r,0_{\mathbb{K}_m},\ldots,0_{\mathbb{K}_m}\right)\] for some linearly independent row vectors \((\vec{\omega}_1,\ldots,\vec{\omega}_r) \in \mathbb{K}_{m}.\) Since the matrix \(\mathbf{B}_N\cdots \mathbf{B}_1\) is invertible, we also obtain a basis \(\{\vec{\xi}_1,\ldots,\vec{\xi}_n\}\) of \(\mathbb{K}_{n}\) so that \[\mathbf{B}_N\cdots \mathbf{B}_1=\Omega(\vec{\xi}_1,\ldots,\vec{\xi}_{n}).\] We now claim that \(\mathcal{S}=\{\vec{\xi}_{r+1},\ldots,\vec{\xi}_n\}\) is a basis of \(U.\) The set \(\mathcal{S}\) is linearly independent, hence we only need to show that \(\operatorname{span}(\mathcal{S})=U.\) Since we have \[\Omega(\vec{\xi}_1,\ldots,\vec{\xi}_n)\mathbf{A}=\Omega\left(\vec{\omega}_1,\ldots,\vec{\omega}_r,0_{\mathbb{K}_m},\ldots,0_{\mathbb{K}_m}\right),\] the definition of matrix multiplication implies that \(\vec{\xi}_i\mathbf{A}=\vec{\omega}_i\) for \(1\leqslant i\leqslant r\) and \(\vec{\xi}_i\mathbf{A}=0_{\mathbb{K}_m}\) for \(r+1\leqslant i\leqslant n.\) Any vector in \(U\) can be written as \(\vec{\nu}=\sum_{i=1}^ns_i\vec{\xi}_i.\) The condition \(\vec{\nu}\mathbf{A}=0_{\mathbb{K}_m}\) then implies that \(s_1=\cdots=s_r=0,\) hence \(\mathcal{S}\) is generating.

We can use this observation to compute the kernel and nullity of a linear map \(\mathbb{K}^n \to \mathbb{K}^m\) because of the following lemma whose proof is left as an exercise.

We simply apply the above procedure to the matrix \(\mathbf{A}=\mathbf{C}^T\) and compute the vectors \(\{\vec{\xi}_{r+1},\ldots,\vec{\xi}_n\}.\) The basis of \(\operatorname{Ker}(f_\mathbf{C})\) is then given by \(\{\vec{\xi}_{r+1}^T,\ldots,\vec{\xi}_n^T\}.\)

The nullity of \(f_\mathbf{C}\) is given by the number of basis vectors of \(\operatorname{Ker}(f_\mathbf{C}).\)

Linear Algebra I

Home

Contents

Exercises

Lecture Recordings

Quizzes

Study Weeks

---

✕