Unsymmetric to Symmetric Tridiagonal Matrix

Question

According to the Wikipedia page here, a real, unsymmetric tridiagonal matrix can be brought to symmetric form by a similarity transform. Does anyone know if a generalization of the formula given there exists for unsymmetric tridiagonal matrices which are

1. complex and Hermitian, and;
2. contain nonzero elements in their upper-right and lower left corners (i.e. which are subject to periodic boundary conditions)

Thank you!

Answer 1

Do you mean that the matrix $M$ in question is a) Hermitian and b) is a sum of a tridiagonal matrix and a matrix $aE_{1n}+a^*E_{n1}$?

A general way that is not using b) would be as follows. You can 1. make $M$ tridiagonal Hermitian, and afterwards then 2. make it real symmetric.

1. Use Householder transformations: for each column $k=1\ldots n-1$, replace $M$ with $VMV$, where $V = \mathrm{diag}(I_k,U_k)$, $U_k = I_{n-k} - \dfrac{2X_k X_k^\dagger}{||X_k||^2}$, $X_k = \dfrac{v_k-\alpha_k (1,0,\ldots,0)^T}{\sqrt{2||v_k||(||v_{n-k}||+|m_{k1}|)}}$, $\alpha_k=\dfrac{||v_k||m_{k1}}{|m_{k1}|}$, and finally $v_k$ is the $(n-k)\times 1$ part of the $k$-th column that is below the diagonal.

Note that the first step ($k=1$) will smear the "boundary condition" entries all across the matrix, except the first column, so you won't be able to stop right after. I'm not sure if it would be computationally feasible for your matrix (you might have a sparse matrix with large $n$), but I also don't know whether this could be avoided. The Givens rotations also introduce nonzero elements away from corners.

2. The matrix is now Hermitian tridiagonal. Make the $m_{21}$ element real by dividing the whole second row by $m_{21}/|m_{21}|$, and then multiplying the second column by the same number. This step was a unitary similarity transformation (by a diagonal matrix). Then repeat the process for $m_{32}, \ldots$

Oh, and by the way: in 1. you should absolutely not calculate $U_k$ as a matrix if you don't want the $O(n^2)$ algorithm to become $O(n^3)$. Just pad the vectors $X_k$ with $k$ zeros and do vector-matrix (rather than matrix-matrix) multiplications with $M$.