An orthogonal similarity reduction of a symmetric matrix to a symmetric semiseparable one

An algorithm to transform a symmetric matrix into a semiseparable one by orthogonal similarity transformations is presented in this section. The constructive proof of the next theorem, provides the algorithm.

Theorem 49   Let $A$ be a symmetric matrix. Then there exists an orthogonal matrix $U$ such that

$$U^TAU=S,$$

where $S$ is a semiseparable matrix.

Proof. The constructive proof made by induction on the rows of the matrix $A$. Let $A_0^{(1)} = A.$ We will often, briefly denote $A_0^{(i)}$ as $A^{(i)}$. Let $G_{i}^{(l)}$ be a Givens transformation, such that the product $A_{i-1}^{(l)} G_{i}^{(l)}$ has the entry $(n-l+1,i)$ annihilated and the $i$th and the $(i+1)$th columns of $A_{i-1}^{(l)}$ modified.

Step $1$

We start by constructing a similarity transformation which makes the last two rows (columns) linearly dependent in the lower (upper) triangular part. To this end, we multiply $A_0^{(1)}$ to the left by ${ G_{1}^{(1)}}^T$ and to the right by ${G_{1}^{(1)}}$ to annihilate the elements in position $(1,n)$ and $(n,1)$ in $A_0^{(1)},$ respectively. The arrows denote the columns and rows which will be affected by transforming the matrix $A_0^{(1)}$ into ${G_1^{(1)}}^T A_0^{(1)}G_1^{(1)}$:

$$\begin{array}{c} \begin{array}{ccccc} \hphantom{\vdots\vdots\... ...times & \cdots & \times & \times \end{array}\right) \end{array} \underrightarrow{ {G_{1}^{(1)}}^T A_{0}^{(1)} G_{1}^{(1)} } \begin{array}{c} \begin{array}{c} \hphantom{ \downarrow} \end... ...times & \cdots & \times & \times \end{array}\right) \end{array}$$

$$\Updownarrow$$

$$\begin{array}{c} \hphantom{A} \\ A_0^{(1)} \end{array} \underrightarrow{ {G_{1}^{(1)}}^T A_{0}^{(1)} G_{1}^{(1)} } \begin{array}{c} \hphantom{A} \\ {A_{1}^{(1)}}. \end{array}$$

Note that $\times$ denotes arbitrary elements of the matrix, while $\otimes$ denotes the elements which will be annihilated by the orthogonal similarity transformation. Summarizing, we obtain that $A_{1}^{(1)} = {G_{1}^{(1)}}^T A_{0}^{(1)} G_{1}^{(1)}.$ Continuing this process of annihilating all the elements in the last row (column), except for the element in position $(n,n-1)$ ($(n-1,n)$), we get

$$% latex2html id marker 33482A_{n-2}^{(1)}= \left( \begin{a... ...es \\ 0 & \cdots & 0 & \times & \times \end{array} \right).$$

Multiplying $A_{n-2}^{(1)}$ to the left by ${G_{n-1}^{(1)}}^T,$ we have the following situation,

$$\begin{array}{r} \hphantom{A_1}\\ \hphantom{\vdots}\\ \hpha... ...\otimes \\ 0 & \cdots & 0 & \times & \times \end{array}\right) \underrightarrow{ {G_{n-1}^{(1)}}^T A_{n-2}^{(1)} } \left( \begin{array}{ccccc} \times & \times & \cdots & \times... ...times & \cdots & \boxtimes & \times & \times \end{array}\right)$$

$$\Updownarrow$$

$$\begin{array}{c} \hphantom{A} \\ A_{n-2}^{(1)} \end{array} \underrightarrow{ {G_{n-1}^{(1)}}^T A_{n-2}^{(1)} } \begin{array}{c} \hphantom{A} \\ \tilde{A}_{n-2}^{(1)}, \end{array}$$

i.e., the last two rows are proportional with exception of the entries in the last two columns, (to emphasize the linear dependency among the rows (columns) we denote by $\boxtimes$ the elements of the matrix belonging to these rows (columns)). Let $\tilde{A}_{n-2}^{(1)} = {G_{n-1}^{(1)}}^T A_{n-2}^{(1)}.$ Multiplying now $\tilde{A}_{n-2}^{(1)}$ to the right by ${G_{n-1}^{(1)}},$ the last two columns become linearly dependent above and on the main diagonal, i.e., the last two columns form an upper semiseparable part. Because of symmetry, the last two rows become linearly dependent below and on the main diagonal and form a lower semiseparable part:

$$% latex2html id marker 33511\begin{array}{c} \begin{array}... ...A} \\ A_{n-1}^{(1)}. %% = A_{0}^{(1)}. \end{array}\end{array}$$

To start the next step, $A_{0}^{(2)}$ is defined as $A_{0}^{(2)} = A_{n-1}^{(1)}.$

Step $k$

Let $k =n-j, \; 1 < j < n.$ Assume by induction that $A_0^{(k)}$ has the lower (upper) triangular part already semiseparable from row $n$ up to row $j+1$ (column $j+1$ to $n$). We will now prove that we can make the lower (upper) triangular part semiseparable up to row $j$ (column $j$). Let us denote the lower (and upper)triangular elements which form a semiseparable part with $\boxtimes.$ Matrix $A_0^{(k)}$ looks like:

$$% latex2html id marker 33539A_0^{(k)}= \left(\begin{array... ...eftarrow & j+1\; . \\ \vdots& \\ \leftarrow & n \end{array}$$

We remark that the lower right $k \times k$ block of $A^{(k)}_0$ is already semiseparable. Because the submatrix of $A_0^{(k)}$ consisting of the first $j$ columns and the last $n-j$ rows is already semiseparable, it has rank $\leq 1$. Hence, we can construct a Givens transformation $G_1^{(k)}$ such that multiplying $A_0^{(k)}$ to the left by ${G_1^{(k)}}^T$ will annihilate all elements $(1,j+1)$, $(1,j+2)$ up to $(1,n)$. In a similar way, we can construct the Givens transformations ${G_{2}^{(k)}}, \ldots, {G_{j-2}^{(k)}}$ and ${G_{j-1}^{(k)}}$ such that multiplying $A_1^{(k)}$ on the left with ${G_{j-1}^{(k)}}^T \ldots {G_{2}^{(k)}}^T$ , will make zero elements in rows $2$ up to $j-1$ the columns $j+1$ up to $n$. Applying these similarity transformations, we obtain the following matrix

$$A^{(k)}_{j-1} = {G_{j-1}^{(k)}}^T \cdots {G_{1}^{(k)}}^T A_{0}^{(k)} G_{1}^{(k)} \cdots G_{j-1}^{(k)}$$

$$= \left(\begin{array}{ccccccc} \times & \cdots & & \times & 0 & \cd... ...eftarrow & j\\ \leftarrow & j+1\; . \\ \vdots& \\ \leftarrow & n \end{array}$$

Since the rows $j$ and $j+1$ are proportional for the indexes of columns greater than $j,$ also the Givens transformation ${G_{j}^{(k)}}^T$ can be constructed, annihilating all the entries in row $j$ with column index greater than $j$. Furthermore, the product of ${G_{j}^{(k)}}^T A^{(k)}_{j-1}$ to the right by ${G_{j}^{(k)}}$ makes the columns $j$ and $j+1$ proportional in the first $j$ entries. The latter similarity transformation is depicted in Figure 4.1.

Figure 4.1: The transformation $A^{(k)}_{j}={G_{j}^{(k)}}^T A^{(k)}_{j-1} {G_{j}^{(k)}}$ makes the first $j$ entries of rows (columns) $j$ and $j+1$ proportional.

To retrieve the semiseparable structure, below the ($j+1$)th row and to the right of the ($j+1$)th column, $n-j-1$ more similarity Givens transformations $G_k$, $k=j+1,j+2,\ldots,n-1$ are considered. Each of these is chosen in such a way that when the Givens transformation $G_k^T$ is applied to the left, the elements $k+1,k+2, \ldots,n$ are annihilated in row $k$, using the corresponding elements of row $k+1$. To obtain a similar matrix, we apply $G_k$ also on the right, thereby adding one more row (column) to the semiseparable part. The whole process is summarized in Figure 4.2.

Figure 4.2: Description of the similarity transformations used to retrieve the semiseparable structure.

This proves the theorem. $\qedsymbol$

In Chapter 6, the details are given how to implement this algorithm using the Givens-vector representation for the semiseparable part of the matrices involved. This will result in an $O(n^3)$ algorithm to compute the Givens-vector representation of a semiseparable matrix similar to the original symmetric matrix. Taking a closer look at the algorithm reveals that the first Givens transformations at each step in the reduction algorithm can be replaced by a corresponding Householder transformation. In step $k=n-j$ of the reduction a similarity transformation of the following form is performed ${G_{j-1}^{(k)}}^T \ldots {G_2^{(k)}}^T A_0^{(k)} G_2^{(k)}\ldots G_{j-1}^{(k)}$ which can be replaced by a single Householder transformation $H^{(k)}$, such that ${H^{(k)}}^T A_0^{(k)} H^{(k)}$ has the same entries annihilated. Moreover we obtain the same result when transforming the symmetric matrix into a tridiagonal one, which costs $4 n^3/3 + O(n^2)$ with Householders, $2 n^3 + O(n^2)$ with Givens transformations and then transforming the tridiagonal matrix to a semiseparable matrix by using Givens transformations, which costs an extra $9 n^2 + O(n)$. This means that we have, in comparison with the tridiagonalization, an extra cost of $9 n^2 + O(n)$. When first reducing matrices to tridiagonal form, intermediate matrices look like:

$$\left(\begin{array}{-at-{}c-at-{\hspace{1.... ... 0 & 0 & 0 & 0 & 0 &{ \boxtimes} & { \boxtimes} &\boxtimes \end{array}. \right)$$

Because the algorithm from Theorem 49, and the algorithm which first tridiagonalizes a symmetric matrix, and afterwards makes a semiseparable matrix from it are essentially the same, one might doubt the usefulness of the reduction to semiseparable form. However, the algorithm of Theorem 49 has some advantages which will become clear in the next chapter.

Once the semiseparable matrix has been computed, several algorithms can be considered to compute its eigenvalues (see, for instance, [35,38,69,130] and the implicit $QR$-algorithm, as considered in this thesis, see Part III, Chapter 8).

The proposed algorithm itself, however, while running to completion, gives already information on the spectrum of the initial matrix. In particular, depending on the distribution of the eigenvalues, often, after few steps of the algorithm, the largest eigenvalues are already approximated with high accuracy. This important feature of the algorithm is analyzed in Chapter 5.