Linear Algebra

This page supports the main stream of the web site by providing/reminding some information regading Linear Algebra. We demonstrate capabilities of MuPad for this topic.

ReflecttionΒΆ

Reflection

Suppose that we are given a line spanned over the vector a in \( \mathbb{R}^n , \) and we need to find a matrix H of reflection about the line through the origin in the plane. This matrix H should fix every vector on line, and should send any vector not on the line to its mirror image about the line. The subspace \( {\bf a}^{\perp} \) is called the hyperplane in \( \mathbb{R}^n , \) orthogonal to a. The \( n \times n \) orthogonal matrix
\[ {\bf H}_{\bf a} = {\bf I}_n - \frac{2}{{\bf a}^{\mathrm T} {\bf a}} \, {\bf a} \, {\bf a}^{\mathrm T} = {\bf I}_n - \frac{2}{\| {\bf a} \|^2} \, {\bf a} \, {\bf a}^{\mathrm T} \]

is called the Householder matrix or the Householder reflection about a, named in honor of the American mathematician Alston Householder (1904--1993). The complexity of the Householder algorithm is \( 2mn^2 - (2/3)\, n^3 \) flops (arithmetic operations). The Householder matrix \( {\bf H}_{\bf a} \) is symmetric, orthogonal, diagonalizable, and all its eigenvalues are 1's except one which is -1. Moreover, it is idempotent: \( {\bf H}_{\bf a}^2 = {\bf I} . \) When \( {\bf H}_{\bf a} \) is applied to a vector x, it reflects x through hyperplane \( \left\{ {\bf z} \, : \, {\bf a}^{\mathrm T} {\bf z} =0 \right\} . \)

Example. We present some simple reflections on the plane and in 3D in the following tables.

Operator
Illustration
Standard Matrix
Reflection about
the x-axis
T(x,y) = (x,-y)
\( \begin{bmatrix} 1&0 \\ 0&-1 \end{bmatrix} \)
Reflection about
the y-axis
T(x,y)=(-x,y)
\( \begin{bmatrix} -1&0 \\ 0&1 \end{bmatrix} \)
Reflection about
the line y=x
T(x,y)=(y,x)
\( \begin{bmatrix} 0&1 \\ 1&0 \end{bmatrix} \)
Operator
Illustration
Standard Matrix
Reflection about
the xy-plane
T(x,y,z) = (x,y,-z)
\( \begin{bmatrix} 1&0&0 \\ 0&1&0 \\ 0&0&-1 \end{bmatrix} \)
Reflection about
the xz-plane
T(x,y,z)=(x,-y,z)
\( \begin{bmatrix} 1&0&0 \\ 0&-1&0 \\ 0&0&1 \end{bmatrix} \)
Reflection about
the yz-plane
T(x,y,z)=(-x,y,z)
\( \begin{bmatrix} -1&0&0 \\ 0&1&0 \\ 0&0&1 \end{bmatrix} \)

Example. Consider the vector \( {\bf u} = \left[ 1, -2 , 2 \right]^{\mathrm T} . \) Then the Householder reflection with respect to vector u is

\[ {\bf H}_{\bf u} = {\bf I} - \frac{2}{9} \, {\bf u} \,{\bf u}^{\mathrm T} = \frac{1}{9} \begin{bmatrix} 7&4&-4 \\ 4&1&8 \\ -4&8&1 \end{bmatrix} . \]
The orthogonal symmetric matrix \( {\bf H}_{\bf u} \) is indeed a reflection because its eigenvalues are -1,1,1, and it is idempotent.

Example. Multiplication by the matrix

\[ {\bf A} = \begin{bmatrix} -1&0 \\ 0& -1 \end{bmatrix} \]

has the geometrical effect of reflecting the unit square about the origin. From the equation

\[ {\bf A} = \begin{bmatrix} -1&0 \\ 0& -1 \end{bmatrix} = \begin{bmatrix} -1&0 \\ 0& 1 \end{bmatrix} \, \begin{bmatrix} 1&0 \\ 0& -1 \end{bmatrix} , \]
it follows that multiplication by A is equivalent to reflection about x-axis and then reflection about the y-axis. On the other hand, multiplication by the matrix
\[ {\bf B} = \begin{bmatrix} 0&-1 \\ -1& 0 \end{bmatrix} \]
reflects about the line y = -x.

Theorem: If u and v are distinct vectors in \( \mathbb{R}^n \) with the same norm, then the Householder reflection about the hyperplane \( \left( {\bf u} - {\bf v} \right)^{\perp} \) maps u into v and conversely. ■

We check this theorem for two-dimensional vectors \( {\bf u} = \left[ u_1 , u_2 \right]^{\mathrm T} \) and \( {\bf v} = \left[ v_1 , v_2 \right]^{\mathrm T} \) of the same norm. So given \( \| {\bf v} \| = \| {\bf u} \| , \) we calculate

\[ \| {\bf u} - {\bf v} \|^2 = \| {\bf u} \|^2 + \| {\bf v} \|^2 - \langle {\bf u}, {\bf v} \rangle - \langle {\bf v} , {\bf u} \rangle = 2 \left( u_1^2 + u_2^2 - u_1 v_1 - u_2 v_2 \right) . \]
Then we apply the Householder reflection \( {\bf H}_{{\bf u} - {\bf v}} \) to the vector u:
\begin{align*} {\bf H}_{{\bf u} - {\bf v}} {\bf u} &= {\bf u} - \frac{2}{\| {\bf u} - {\bf v} \|^2} \begin{bmatrix} \left( u_1 - v_1 \right)^2 u_1 + \left( u_1 - v_1 \right) \left( u_2 - v_2 \right) u_2 \\ \left( u_1 - v_1 \right) \left( u_2 - v_2 \right) u_1 + \left( u_2 - v_2 \right)^2 u_2 \end{bmatrix} \\ &= \frac{1}{u_1^2 + u_2^2 - u_1 v_1 - u_2 v_2} \begin{bmatrix} v_1 \left( u_1^2 + u_2^2 - u_1 v_1 - u_2 v_2 \right) \\ v2 \left( u_1^2 + u_2^2 - u_1 v_1 - u_2 v_2 \right) \end{bmatrix} = {\bf v} . \end{align*}
Similarly, \( {\bf H}_{{\bf u} - {\bf v}} {\bf v} = {\bf u} . \)

Example. We find a Householder reflection that maps the vector \( {\bf u} = \left[ 1, -2 , 2 \right]^{\mathrm T} \) into a vector v that has zeroes as its second and third components. Since this vecor has to be of the same norm, we get \( {\bf v} = \left[ 3, 0 , 0 \right]^{\mathrm T} . \) Since \( {\bf a} = {\bf u} - {\bf v} = \left[ -2, -2 , 2 \right]^{\mathrm T} , \) the Householder reflection \( {\bf H}_{{\bf a}} = \frac{1}{3} \begin{bmatrix} 1&-2&2 \\ -2&1&2 \\ 2&2&1 \end{bmatrix} \) maps the vector \( {\bf u} = \left[ 1, -2 , 2 \right]^{\mathrm T} \) into a vector v. Matrix \( {\bf H}_{{\bf a}} \) is idempotent (\( {\bf H}_{{\bf a}}^2 = {\bf I} \) ) because its eigenvalues are -1, 1, 1. ■

sage: nsp.is_finite()
False

We use the Householder reflection to obtain an alternative version of LU-decomposition. Consider the following m-by-n matrix:

\[ {\bf A} = \begin{bmatrix} a & {\bf v}^{\mathrm T} \\ {\bf u} & {\bf E} \end{bmatrix} , \]
where u and v are m-1 and n-1 vectors, respectively. Let σ be the 2-norm of the first column of A. That is, let
\[ \sigma = \sqrt{a^2 + {\bf u}^{\mathrm T} {\bf u}} . \]
Assume that σ is nonzero. Then the vector u in the matrix A can be annihilated using a Householder reflection given by
\[ {\bf P} = {\bf I} - \beta {\bf h}\, {\bf h}^{\mathrm T} , \]
where
\[ {\bf h} = \begin{bmatrix} 1 \\ {\bf z} \end{bmatrix} , \quad \beta = 1 + \frac{a}{\sigma_a} , \quad {\bf z} = \frac{\bf u}{\beta \sigma_a} , \quad \sigma_a = \mbox{sign}(a) \sigma . \]
It is helpful in what follows to define the vectors q and p as
\[ {\bf q} = {\bf E}^{\mathrm T} {\bf z} \qquad\mbox{and} \qquad {\bf p} = \beta \left( {\bf v} + {\bf q} \right) . \]
Then
\[ {\bf P}\,{\bf A} = \begin{bmatrix} \alpha & {\bf w}^{\mathrm T} \\ {\bf 0} & {\bf K} \end{bmatrix} , \]
where
\[ \alpha = - \sigma_a , \quad {\bf w}^{\mathrm T} = {\bf v}^{\mathrm T} - {\bf p}^{\mathrm T} , \quad {\bf K} = {\bf E} - {\bf z}\,{\bf p}^{\mathrm T} . \]

The above formulas suggest the following version of Householder transformations that access the entries of the matrix in a row by row manner.

Algorithm (Row-oriented vertion of Householder transformations):

Step 1: Compute \( \sigma_a \) and β

\[ \sigma = \sqrt{a^2 + {\bf u}^{\mathrm T} {\bf u}} , \qquad \sigma_a = \mbox{sign}(a) \,\sigma , \qquad \beta = a + \frac{a}{\sigma_a} . \]

Step 2: Compute the factor row \( \left( \alpha , {\bf w}^{\mathrm T} \right) : \)

\[ \alpha = - \sigma_a , \qquad {\bf z} = \frac{\bf u}{\beta \sigma_a} . \]
Compute the appropriate linear combination of the rows of A (except for the first column) by computing
\[ {\bf q}^{\mathrm T} = {\bf z}^{\mathrm T} {\bf E}, \qquad {\bf p}^{\mathrm T} = \beta \left( {\bf v}^{\mathrm T} + {\bf q}^{\mathrm T} \right) , \qquad {\bf w}^{\mathrm T} = {\bf v}^{\mathrm T} - {\bf p}^{\mathrm T} . \]

Step 3: Apply Gaussian elimination using the pivot row and column from step 2:

\[ \begin{bmatrix} 1 & {\bf p}^{\mathrm T} \\ {\bf z} & {\bf E} \end{bmatrix} \, \rightarrow \, \begin{bmatrix} 1 & {\bf p}^{\mathrm T} \\ {\bf 0} & {\bf K} \end{bmatrix} , \]
where \( {\bf K} = {\bf E} - {\bf z} \,{\bf p} ^{\mathrm T} . \)

This formulation of Householder transformations can be regarded as a special kind of Gauss elimination, where the pivot row is computed from a linear combination of the rows of the matrix, rather than being taken directly from it. The numerical stability of the process can be seen from the fact that \( |z_i | \le 1 \) and \( |w_j | \le \beta \le 2 \) for every entry in z and w.

The Householder algorithm is the most widely used algorithm for QR factorization (for instance, qr in MATLAB) because it is less sensitive to rounding error than Gram--Schmidt algorithm.