Problem 4 - Numerical Calculus

For $n$-dimensional vectors $a$,$b$ $(a\neq b)$ of the same length, an $n \times n$ matrix $P$ defined by

$$P = I - 2 uu^T, \quad u = (a-b)/\vert\vert a-b\vert\vert$$

is called a Householder matrix. Answer the following questions.

1.

Show $b = Pa$, $a = Pb$.

2.

Show $P$ is an orthogonal matrix.

3.

Find all the eigenvalues of $P$.

4.

Compute the determinant of $P$.

1.

$Pa = (I-2uu^T)a$
$= a - 2 \frac{a-b}{\vert\vert a-b\vert\vert}\frac{a^T - b^T}{\vert\vert a-b\vert\vert}a$
$= a - 2 (a - b)\frac{a^Ta - b^Ta}{\vert\vert a-b\vert\vert^2}$
$= a - 2 (a - b)\frac{\vert\vert a\vert\vert^2 - b^Ta}{\vert\vert a\vert\vert^2 + \vert\vert b\vert\vert^2 - a^Tb - b^Ta}$
$= a - (a - b)\frac{2\vert\vert a\vert\vert^2 - 2<a\vert b>}{\vert\vert a\vert\vert^2 + \vert\vert b\vert\vert^2 - 2<a\vert b>}$
$= a - (a-b)$, since $a$ and $b$ have the same length.
$= b$
We show that $Pb = a$ is a similar way.

2.

$P = I - 2 u u^T$ that we can also write:

$$P = \left( \begin{tabular}{cccc} $1-2u_1^2$ & $-2u_1u_2$ & $\cdot... ...\\ $-2u_nu_1$ & $-2u_nu_2$ & $\cdots$ & $1-2u_n^2$ \\ \end{tabular} \right)$$

$P$ is symmetric. To determine whether or not it is orthogonal, we form $PP^T = P^2$.

Let $\mathcal{L}_i$ be a line of $P$ and $\mathcal{C}_j$ be a column of $P$. The $k$th element of $\mathcal{L}_i$ is equal to $-2u_iu_k$ if $i\neq k$ and to $1-2u_i^2$ if $i=k$. The $k$th element of $\mathcal{C}_j$ is equal to $-2u_ku_j$ if $j\neq k$ and to $1-2u_j^2$ if $i=k$.

Suppose we look for an element $(i,i)$ of the matrix $P^2$. This element is:

$$\mathcal{L}_i.\mathcal{C}_i = 1 + 4u_i^4 - 4u_i^2 + \sum_{k=1; k\neq i}^n 4 u_i^2u_k^2$$

$$= 1 - 4 u_i^2 + \sum_{k=1}^n 4 u_i^2u_k^2$$

$$= 1 - 4 u_i^2 + 4 u_i^2 \sum_{k=1}^n u_k^2$$

$$= 1 - 4 u_i^2 + 4 u_i^2, \quad \hbox{since} \; \vert\vert u\vert\vert^2 = 1$$

$$= 1$$

Now, we look for an element $(i,j)$ $(i\neq j)$ of the matric $P^2$. This element is:

$$\mathcal{L}_i.\mathcal{C}_j = \sum_{k=1;k\neq i,j}^n 4 u_iu_ju_k^2 - 2(1-2u_i^2)u_iu_j - 2(1-2u_j^2)u_ju_i$$

$$= \sum_{k=1;k\neq i,j}^n 4 u_iu_ju_k^2 - (2u_iu_j - 4 u_i^3u_j)- (2u_ju_i - 4u_j^3u_i)$$

$$= 4 u_iu_j\sum_{k=1}^n u_k^2 - 2u_iu_j - 2u_ju_i$$

$$= 4 u_iu_j - 4u_iu_j$$

$$=0$$

And thus $PP^T=I$ and $P$ is orthogonal.

3.

Let $\lambda$ be an eigenvalue of $P$. We have a vector $x$ such that:
$Px = \lambda x$
$P^2 x = \lambda P x = \lambda^2 x = x$
Therefore, $\lambda^2 = 1$ and $\lambda \in \{ -1,+1 \}$

4.

Since $PP^T=I$:
$\det P \det P^T = (\det P)^2 = \det I = 1$
Then, $\det P \in \{-1,+1\}$