# Uniqueness of Hessenberg matrix in Cholesky factorization of Hankel matrix

I'm reading the paper how bad are Hankel matrices?, where the author claimed the following:

Lemma 2.1. For any positive definite Hankel matrix $$H \in \mathbb{R}^{n \times n}$$ there exist a Vandermonde matrix $$V \in \mathbb{R}^{n \times n}$$ and a diagonal $$\Lambda \in \mathbb{R}^{n \times n}$$ such that $$H=V \Lambda^2 V^{\mathrm{T}} .$$

Proof. Since $$H$$ is positive definite, we may consider the Cholesky decomposition of it: $$H=R^{\mathrm{T}} R,$$ where $$R \in \mathbb{R}^{n \times n}$$ is upper triangular. Following [4], we are now going to find an upper Hessenberg matrix $$T$$ such that $$r_{11}^{-1} R=\left[e_1, T e_1, \ldots, T^{n-1} e_1\right], \tag{2.4}$$ where $$e_1=[1,0, \ldots, 0]^{\mathrm{T}}$$. It is evident that all $$T$$ 's columns, save for the last one, are uniquely determined from (2.4). The last column can be arbitrary, and we take it such that $$T e_n=T^{\mathrm{T}} e_n,$$ ....

The author stated that it is evident that all $$T's$$ columns, save for the last one, are uniquely determined from (2.4), but I have no idea why that is the case. I also don't understand why the last column can be arbitrary.

Perhaps this is due to some special property of powers of the Hessenberg matrix?

• The first column of $$T$$ is of course $$Te_1$$, and so is determined by (2.4).
• If $$T$$ is unreduced, upper Hessenberg matrix, then $$Te_1 = a e_1 + be_2$$ for some $$a, b$$, with $$b \neq 0$$ (due to unreducedness). Hence $$T^2 e_1 = a Te_1 + b Te_2 \Rightarrow Te_2 = \frac{1}{b} (T^2 e_1 - a Te_1).$$ Since (2.4) pinned down $$T^2 e_1$$ and $$Te_1$$ (hence $$b$$, the second entry of $$Te_1$$), we see that $$Te_2$$ is pinned down as well; i.e. the second column of $$T$$ is pinned down.
You can iterate this argument to see that for $$i = 1, \cdots, n-1$$, the $$i$$-th column of $$T$$ (i.e. $$Te_i$$) is pinned down by $$Te_1, \cdots, T^i e_1$$ recursively.
Finally, the above argument also shows that $$span(Te_1, \cdots, T^{n-1}e_1) = span(Te_1, \cdots, Te_{n-1}).$$ In particular, the information of $$Te_1, \cdots, T^{n-1}e_1$$ does not constrain on the $$n$$-th column of $$T$$. The upper Hessenberg property does not impose extra constraint on this last column either; so the last column can be arbitrary.
This is not $$\textit{very}$$ evident, but it does come down to a cool property of powers of Hessenberg matrices and induction: Suppose we have a "Hessenberg upper triangular-like matrix" $$M$$ where the lack of being upper triangular can be something other than $$1$$ from the diagonal--in other words, there is some $$d$$ such that $$M_{ij}$$ is $$0$$ if $$i > j + d$$. For Hessenberg matrices, $$d=1$$. However, in the general case, if you multiply on the left by a Hessenberg matrix, you see that the resulting matrix has a d value of one greater than what $$M$$ had. Consider powers of Hessenberg matrices. The first powers left column has two elements and is completely determined by the LHS. The second's has three elements and is determined completely LHS. The latter determines the second column of the Hessenberg matrix because we have already chosen the first column. The proof is complete when you realize the left column of each power of a Hessenberg matrix has (the power $$+1$$) elements, which are themselves determined by the first (power) columns of the matrix. However, the first (power $$-1$$) columns have already been determined. So the $$n$$th power determines the $$n$$th column of the Hessenberg matrix.