# Determine a sufficient condition for a Hessenberg matrix to be nonsingular

Consider $A\in\mathbb{R}^{n\times n}$ whose nonzero elements are restricted to the main diagonal the strict upper triangular part, and the first subdiagonal. For $n = 8$ the locations that must be zero are indicated and the positions that may be nonzero are indicated by $\alpha_{ij}$: $$\begin{pmatrix} \alpha_{11} & \alpha_{12} & \alpha_{13} & \alpha_{14} & \alpha_{15} & \alpha_{16} & \alpha_{17} & \alpha_{18}\\ \alpha_{21} & \alpha_{22} & \alpha_{23} & \alpha_{24} & \alpha_{25} & \alpha_{26} & \alpha_{27} & \alpha_{28}\\ 0 & \alpha_{32} & \alpha_{33} & \alpha_{34} & \alpha_{35} & \alpha_{36} & \alpha_{37} & \alpha_{38}\\ 0 & 0 & \alpha_{43} & \alpha_{44} & \alpha_{45} & \alpha_{46} & \alpha_{47} & \alpha_{48}\\ 0 & 0 & 0 & \alpha_{54} & \alpha_{55} & \alpha_{56} & \alpha_{57} & \alpha_{58}\\ 0 & 0 & 0 & 0 & \alpha_{65} & \alpha_{66} & \alpha_{67} & \alpha_{68}\\ 0 & 0 & 0 & 0 & 0 & \alpha_{76} & \alpha_{77} & \alpha_{78}\\ 0 & 0 & 0 & 0 & 0 & 0 & \alpha_{87} & \alpha_{88}\\ \end{pmatrix}$$

i.) Suppose the subdiagonal elements $\alpha_{i+1,i} \neq 0$ (this is called an unreduced Hessenberg matrix). Determine a necessary and sufficient condition for $A$ to be nonsingular.

Attempted solution - If $\det(A)\neq 0$ then $A$ is nonsingular.

ii.) Describe an efficient algorithm to solve $Ax = b$ via factorization and determine the order computational complexity, i.e., give $k$ in $O(n^k)$. Your solution should include a description of how you exploit the structure of the matrix and how it influences the structure of your factors.

Attempted solution - I am thinking of just using the $LU$ factorization and getting $A$ such that $A = L + D + L^T$ then I can just calculate $Lx$, $Dx$, and $L^T x$ and sum the results (Carl Christian) recommended this in another exercise.

Also since $A$ is almost upper trapezoidal we could simply apply the Gauss transform matrices $M_1, M_2,\ldots, M_7$ to get $U$ then we can easily find $L$ and then we would just use a forward and backward solve to compute $Ax = b$. This will still result in $O(n^2)$ computations.

Anyways these type of questions are challenging for me, if anyone has any suggestions I would greatly appreciate it. Also, I want to know what constitutes as a complete solution for b.) as in what do I need to show in my solution to satisfy the conditions asked.

• Hints. 1) What is a simple condition for a triangular matrix to be nonsingular? 2) How might you convert a Hessenberg matrix into a triangular matrix? – Richard Zhang Jun 2 '16 at 15:38
• For 1) if the determinant of a matrix is non zero then it is nonsingular. 2) we can convert the Hessenberg matrix into a triangular matrix by multiplying the Gaussian transform matrices in which I described above – Wolfy Jun 2 '16 at 16:27
• And what's the determinant of a triangular matrix? – Steve Jun 2 '16 at 22:04
• The determinant of a triagular matrix is the product of the diagonal entries – Wolfy Jun 3 '16 at 15:01

Write

$$\mathrm{A} = \begin{bmatrix} \mathrm{r}^{\top} & \alpha_{18}\\ \mathrm{U} & \mathrm{c}\end{bmatrix}$$

where $\mathrm{U} \in \mathbb{R}^{(n-1) \times (n-1)}$ is an upper triangular matrix. There is a permutation matrix $\mathrm{P}$ such that

$$\mathrm{\mathrm{A}} \mathrm{\mathrm{P}} = \begin{bmatrix} \alpha_{18} & \mathrm{r}^{\top}\\ \mathrm{c} & \mathrm{U}\end{bmatrix}$$

whose determinant is

$$\det (\mathrm{AP}) = \det (\mathrm{A}) \cdot \underbrace{\det(\mathrm{P})}_{=\pm1} = \det (\mathrm{U}) \cdot (\alpha_{18} - \mathrm{r}^{\top} \mathrm{U}^{-1} \mathrm{c})$$

As $\mathrm{U}$ is upper triangular, its determinant is the product of its entries on the main diagonal. Thus, if there are no zero entries on the main diagonal of $\mathrm{U}$, then $\mathrm{U}$ is invertible. If $\mathrm{U}$ is invertible and $\alpha_{18} \neq \mathrm{r}^{\top} \mathrm{U}^{-1} \mathrm{c}$, then we have $\pm \det (\mathrm{A}) \neq 0$, i.e., $\mathrm{A}$ is non-singular. To summarize, we have the following sufficient condition

$$\left(\displaystyle\prod_{i=1}^{n-1} u_{ii} \neq 0\right) \land \left(\alpha_{18} \neq \mathrm{r}^{\top} \mathrm{U}^{-1} \mathrm{c}\right)$$

Note that if $\mathrm{U}$ is invertible, then $\mathrm{U}^{-1} \mathrm{c}$ is the unique solution to the linear system $\mathrm{U} \mathrm{y} = \mathrm{c}$, whose augmented matrix is $[\mathrm{U}\,|\,\mathrm{c}]$, which is a submatrix of $\mathrm{A}$ (namely, its last $n-1$ rows).

• You can strengthen your proof to show that you condition is both necessary and sufficient. Suppose the block matrix $M = \begin{bmatrix} A & B \\ C & D \end{bmatrix}$ has $A$ nonsingular, then $M$ is row equivalent to $\begin{bmatrix} I & A^{-1}B \\ 0 & S \end{bmatrix}$ where $S = D - CA^{-1} B$. Hence $A$ is nonsingular if and only if $S$ is nonsingular. Your approach is perfectly fine, it is force of habit which has me forming the Schur complement in the lower right corner rather than the upper left corner. Kind regards – Carl Christian Jun 3 '16 at 19:59
• I am sure this solution is correct I just don't understand it at all and I would have no idea how to duplicate this approach towards a similar problem. – Wolfy Jun 4 '16 at 13:21
• @CarlChristian just curious if you would be able to tutor me on Skype for $x an hour but I assume you are probably too busy. Let me know if you would be interested although. – Wolfy Jun 4 '16 at 13:29 • @Wolfy I am merely permuting the columns so that I get a "nice" block matrix. The original matrix wasn't "nice enough" because it didn't have square blocks in the northwest and southeast corners. – Rodrigo de Azevedo Jun 4 '16 at 13:55 • @Wolfy$\mathrm{U}$has that name because it's upper triangular. Don't think of$\mathrm{A}\$ as an "almost upper triangular" matrix with a nonzero subdiagonal. Think of it as an upper triangular matrix to which a row and a column were "glued":$$\left[\begin{array}{ccccccc|c} * & * & * & * & * & * & * & \alpha_{18}\\ \hline * & * & * & * & * & * & * & *\\ 0 & * & * & * & * & * & * & *\\ 0 & 0 & * & * & * & * & * & *\\ 0 & 0 & 0 & * & * & * & * & *\\ 0 & 0 & 0 & 0 & * & * & * & *\\ 0 & 0 & 0 & 0 & 0 & * & * & *\\ 0 & 0 & 0 & 0 & 0 & 0 & * & *\\ \end{array}\right]$$ – Rodrigo de Azevedo Jun 4 '16 at 14:27