Linear Systems of Algebraic Equations

This page presents some topics from Linear Algebra needed for construction of solutions to systems of linear algebraic equations and some applications. We use matrices and vectors as essential elements in obtaining and expressing the solutions.

Gram-Schmidt

In many applications, problems could be significantly simplified by choosing an appropriate basis in which vectors are orthogonal to one another. The Gram–Schmidt process is a method for orthonormalising a set of vectors in an inner product space, most commonly the Euclidean space \( \mathbb{R}^n \) equipped with the standard inner product. The Gram–Schmidt process takes a finite, linearly independent set \( S = \{ {\bf u}_1 , \ldots , {\bf u}_k \} \) for \( k \le n \) and generates an orthogonal set \( S' = \{ {\bf v}_1 , \ldots , {\bf v}_k \} \) that spans the same k-dimensional subspace of \( \mathbb{R}^n \) as S.

The method is named after a Danish actuary Jørgen Pedersen Gram (1850-1916) and a German mathematician Erhard Schmidt (1875-1959) but it appeared earlier in the work of Laplace and Cauchy. The complexity of the Gram--Schmidt algorithm is \( 2mn^2 \) flops (floating point arithmetic operations).  

Before presenting the Gram--Schmidt process, we recall the projection of the vector v on u:

\[ \mbox{proj}_{\bf u} ({\bf v}) = \frac{\langle {\bf v} , {\bf u} \rangle}{\langle {\bf u} , {\bf u} \rangle}\,{\bf u} = \frac{\langle {\bf v} , {\bf u} \rangle}{\| {\bf u} \|^2} \,{\bf u} , \]

where \( \langle {\bf v} , {\bf u} \rangle \) denotes the inner product of the vectors v and u. This operator projects the vector v orthogonally onto the line spanned by vector u.

Gram--Schmidt process converts a basis \( S = \{ {\bf u}_1 , \ldots , {\bf u}_k \} \) into an orthogonal basis \( S' = \{ {\bf v}_1 , \ldots , {\bf v}_k \} \) by performing the following steps:

\begin{align*} {\bf v}_1 &= {\bf u}_1 , \\ {\bf v}_2 &= {\bf u}_2 - \frac{\langle {\bf v}_1 , {\bf u}_2 \rangle}{\| {\bf v}_1 \|^2} \, {\bf v}_1 = {\bf u}_2 - \mbox{proj}_{{\bf v}_1} ({\bf u}_2 , \\ {\bf v}_3 &= {\bf u}_3 - \frac{\langle {\bf v}_1 , {\bf u}_3 \rangle}{\| {\bf v}_1 \|^2} \, {\bf v}_1 - \frac{\langle {\bf v}_2 , {\bf u}_3 \rangle}{\| {\bf v}_2 \|^2} \, {\bf v}_2 = {\bf u}_3 - \mbox{proj}_{{\bf v}_1} ({\bf u}_3 ) - \mbox{proj}_{{\bf v}_2} ({\bf u}_3 ) , \\ \vdots & \quad \vdots \\ {\bf v}_k &= {\bf u}_k - \sum_{j=1}^{k-1} \mbox{proj}_{{\bf v}_j} ({\bf u}_k) . \end{align*}

To convert the orthogonal basis into an orthonormal basis \( \{ {\bf q}_1 = {\bf v}_1 / \| {\bf v}_1 \| , \ldots , {\bf q}_k = {\bf v}_k / \| {\bf v}_k \| , \) normalize the orthogonal basis vectors.

Example. Assume that the vector space \( \mathbb{R}^3 \) has the Euclidean inner product. Apply the Gram-Schmidt process to transform the basis vectors

\[ {\bf u}_1 = \left[ 2, 1, 1 \right]^{\mathrm T} , \quad {\bf u}_2 = \left[ 1, 2, 1 \right]^{\mathrm T} , \quad {\bf u}_3 = \left[ 1, 1, 2 \right]^{\mathrm T} \]

into an orthogonal basis \( \{ {\bf v}_1 , {\bf v}_2 , {\bf v}_3 \} , \) and then normalize the orthogonal basis vectors to obtain an orthonormal basis \( \{ {\bf q}_1 , {\bf q}_2 , {\bf q}_3 \} . \)

Solution. Step 1: \( {\bf v}_1 = {\bf u}_1 = \left[ 2, 1, 1 \right]^{\mathrm T} , \) with \( \| {\bf v}_1 \| = \| \left[ 2, 1, 1 \right] \| = \sqrt{6} . \)
Step 2: Vector \( {\bf v}_2 = {\bf u}_2 - \frac{\langle {\bf v}_1 , {\bf u}_2 \rangle}{\| {\bf v}_1 \|^2} \, {\bf v}_1 = {\bf u}_2 - \frac{5}{6}\,{\bf u}_1 = \frac{1}{6} \left[ -4, 7, 1 \right]^{\mathrm T} . \) We can drop factor 1/6 and consider vector \( {\bf v}_2 = \left[ -4, 7, 1 \right]^{\mathrm T} . \)
Step 3: \( {\bf v}_3 = {\bf u}_3 - \frac{\langle {\bf v}_1 , {\bf u}_3 \rangle}{\| {\bf v}_1 \|^2} \, {\bf v}_1 - \frac{\langle {\bf v}_2 , {\bf u}_3 \rangle}{\| {\bf v}_2 \|^2} \, {\bf v}_2 = \frac{4}{11} \left[ -1, -1, 3 \right]^{\mathrm T} . \) We can drop factor 4/11 and set \( {\bf v}_3 = \left[ -1, -1, 3 \right]^{\mathrm T} . \)
Step 4: Normalization: \( {\bf q}_1 = \frac{{\bf v}_1}{ \| {\bf v}_1 \|} = \frac{1}{\sqrt{6}} \left[ 2, 1, 1 \right]^{\mathrm T} , \) \( {\bf q}_2 = \frac{{\bf v}_2}{ \| {\bf v}_2 \|} = \frac{1}{\sqrt{66}} \left[ -4, 7, 1 \right]^{\mathrm T} , \) and \( {\bf q}_3 = \frac{{\bf v}_3}{ \| {\bf v}_3 \|} = \frac{1}{\sqrt{11}} \left[ -1, -1, 3 \right]^{\mathrm T} . \) ■

Example. Let \( L\,:\, \mathbb{R}^3 \, \mapsto \, \mathbb{R}^3 \) be the orthogonal projection onto the plane \( W: \, 4x-y +8z =0 . \) Then \( {\bf n} = \left[ 4, -1, 8 \right]^{\mathrm T} \) be the normal vector to the plane W. For every vector z spanned on n, \( {\bf z} \in W^{\perp} . \) Hence, \( L({\bf z}) = {\bf 0}, \) since ker(L) = \( W^{\perp} . \)

Now every vector in the plane W is mapped to itself by L. In fact, W equals the eigenspace \( E_1 \) corresponding to the double eigenvalue \( \lambda_1 =1 . \) Thus, finding a basis for W will give us a basis for \( E_1 . \) Let \( {\bf u}_1 = \left[ 1, 4, 0 \right]^{\mathrm T} \) and \( {\bf u}_2 = \left[ 2, 0, 1 \right]^{\mathrm T} \) be two linearly independent vectors in W. They are not orthogonal, so we use Gram--Schmidt procedure to obtain two orthogonal vectors in W: \( {\bf v}_1 = \left[ 1, 4, 0 \right]^{\mathrm T} \) and \( {\bf v}_2 = \left[ 32, -8, -17 \right]^{\mathrm T} \) that form a basis in W.

The projection operator/matrix onto W should have one double (not defective) eigenvalue \( \lambda_1 =1 \) with eigenspace spanned on \( {\bf v}_1 \) and \( {\bf v}_2 \) and one simple eigenvalue \( \lambda_2 =0 \) with eigenspace spanned on the normal vector n. Since these three vectors form a basis for \( \mathbb{R}^3 , \) we build a transition matrix from these eigenvectors:

\[ {\bf S} = \begin{bmatrix} 1&32&4 \\ 4&-8&-1 \\ 0&-17&8 \end{bmatrix} \quad \mbox{with} \quad {\bf S}^{-1} = \frac{1}{1377} \begin{bmatrix} 81&324&0 \\ 32&-8&-17 \\ 324&-17& 136 \end{bmatrix} . \]

Let \( {\bf \Lambda} = \begin{bmatrix} 1&0&0 \\ 0&1&0 \\ 0&0&0 \end{bmatrix} \) be the diagonal matrix of eigenvalues of the projection operator L, then its orthogonal projection matrix becomes

\[ {\bf P} = {\bf S} \, {\bf \Lambda} \, {\bf S}^{-1} = \frac{1}{81} \begin{bmatrix} 65&4&-32 \\ 4&80&8 \\ -32&8&17 \end{bmatrix} . \]

We ask Sage to prove that P is an orthogonal projection matrix, which requires verification that it is symmetric, idempotent, has eigenvalues only 1 and 0, minimal polynomial \( \psi (\lambda ) = \lambda \left( \lambda -1 \right) , \) and its column vectors are orthogonal:

sage: P*P-P 

Finally, we build the orthogonal reflection through the plane W. We have all ingredients to find this matrix: the transition matrix S and its inverse. The only difference reflection has compaired to projection on W is that a vector v orthogonal to the plane will be mapped into its opposite but not into 0. Therefore, the orthogonal reflection matrix will have eigenvalues 1,1, and -1, and the diagonal matrix of eigenvalues will be \( {\bf \Lambda} = \begin{bmatrix} 1&0&0 \\ 0&1&0 \\ 0&0&-1 \end{bmatrix} . \) This allows us to find the reflection matrix:

\[ {\bf Q} = {\bf S} \, {\bf \Lambda} \, {\bf S}^{-1} = \frac{1}{81} \begin{bmatrix} 49&8&-64 \\ 8&79&16 \\ -64&16&-47 \end{bmatrix} . \]

Now we ask Sage to verify that \( {\bf Q}^2 = {\bf I} , \) the identity matrix and that \( {\bf Q}{\bf n} = -{\bf n} \) while \( {\bf P}{\bf n} = {\bf 0} . \)

sage: P*P-P 

QR-decomposition