Determine a sufficient condition for a Hessenberg matrix to be nonsingular

Question

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.

Answer 1

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).