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? 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 Jun 2 '16 at 16:27
• And what's the determinant of a triangular matrix? Jun 2 '16 at 22:04
• The determinant of a triagular matrix is the product of the diagonal entries 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 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. 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. 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. 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]$$ Jun 4 '16 at 14:27