Similar matrix whose square is a Hessenberg matrix

Question

I have a known matrix $\mathbf{A}\in \mathbb{R}^{n \times n}$. I want to find a way to obtain a matrix $\mathbf{B}$ that is similar to $\mathbf{A}$ such that $\mathbf{B^2}$ is a Hessenberg matrix. Please consider that I do not want to calculate the eigenvalues of $\mathbf{A}$ in the process. Thanks

Answer 1

If $A$ has only nonnegative real eigenvalues, you can simply compute the Hessenberg reduction $H$ of $A^2$ and then let $B = \sqrt{H}$ (the matrix square root). (Practical algorithms for these steps do not require eigendecomposition. Moreover, matrix square-root algorithms typically begin by Schur factorization, e.g. how Julia does it, and since Schur factorization typically begins with Hessenberg factorization you can compute the matrix square root of a Hessenberg matrix more quickly than for a general matrix. In fact, Julia exploits this for you, so if you do B = sqrt(hessenberg(A^2).H) in Julia then it should be pretty efficient.)

However, if you have complex or negative eigenvalues, this may take the wrong branch cut of the square root, so the $B$ won't be similar to $A$. So, a more general solution is simply to let $B$ be the triangular matrix $T$ from the complex Schur factorization of $A$, e.g. B = schur(complex(A)).T in Julia, since the square of a triangular matrix is triangular (which is a stronger condition than upper Hessenberg).

Of course, since all of these algorithms involve a Schur factorization, and Schur factorizations tell you the eigenvalues, you have implicitly computed the eigenvalues of $A$. On the other hand, you haven't computed eigenvectors of $A$, i.e. you haven't diagonalized $A$. This is good because if $A$ is nearly defective, then using a diagonalization of $A$ to compute $B$ may be very inaccurate in finite-precision arithmetic.