Is there some way to easily diagonalize a rank-$n$ bisymmetric Toeplitz matrix with only zeros on its main diagonal? Direct calculation is out of the question. I need some trick.

Addendum: I don't know why I didn't do it before, but I can write the matrix down.

$$A= \begin{pmatrix} 0 & 1 & 1/2 & 1/3 & \cdots & 1/(n-1) \\ 1 & 0 & 1 & 1/2 & \cdots & 1/(n-2) \\ 1/2 & 1 & 0 & 1 & \cdots & 1/(n-3) \\ \vdots & & \vdots & \ & \ddots & \vdots \\ 1/i & \cdots & 1/|i-j| &\cdots& & 1/(n-i) \\ \vdots & & \vdots & \ & & \vdots \\ 1/(n-1) & \cdots & 1/3 & 1/2 & 1 & 0\\ \end{pmatrix}$$

or, simpler yet

$$A_{i,j}=\begin{cases} 0 & i=j \\ \frac{1}{|i-j|} & i,j=1\dots n\\ \end{cases}$$

  • $\begingroup$ I think you can diagonalize a circulant matrix by the DFT matrix. $\endgroup$ – yoki Jan 15 '13 at 18:43
  • $\begingroup$ It's bisymmetric but non circulant unfortunately... $\endgroup$ – Alessandro Gadaleta Jan 15 '13 at 19:00
  • $\begingroup$ The usual approach would be to reduce it (by orthogonal similarity) to a tridiagonal form, and diagonalize that. May I assume this approach is what you reject when you write that "[d]irect calculation is out of the question"? $\endgroup$ – hardmath Jan 16 '13 at 14:19
  • $\begingroup$ Well, the point is that I have no idea how to do that in practice! I've benne trying Gaussian elimination without success... maybe I should clarify that I'm actually an experimental physicist and I'm not really used to this kind of calculations... $\endgroup$ – Alessandro Gadaleta Jan 16 '13 at 14:40
  • $\begingroup$ Well, welcome to Math.SE! There's a standard trick for turning a bisymmetric matrix of size $2n \times 2n$ into two $n \times n$ blocks, see e.g. Structured Eigenvalue Problems in Sec. 3.4. I'll try my hand at writing up something for you. A good search term is "structure preserving" when you have very special matrices as here, i.e. depending on a small number of parameters. $\endgroup$ – hardmath Jan 16 '13 at 14:56

A real symmetric matrix has a full basis of orthonormal eigenvectors, so given $A$ as defined in the question, there exists real orthogonal matrix $U$ such that $U^T A U$ is diagonal. For reasons outlined here the practical methods for computing the eigenvalues and eigenvectors of matrices are iterative rather than "direct" (in the sense of giving an explicit formula).

The premise of the SciComp.SE question linked above is that iterative methods for real symmetric matrix eigenvalue/diagonalization typically begin by reducing to a similar (real symmetric) tridiagonal form using Householder transformations, or in some cases Givens rotations, another type of real orthogonal matrix. Orthogonal matrices are desirable not merely because one gets their matrix inverse cheaply (by taking the transpose) but because their numerical error properties are advantageous (multiplication by an orthogonal matrix preserves the length of a vector, and this has a benefit also in controlling the growth of rounding errors).

While the tridiagonalization process is direct, getting from there to a diagonal matrix is where iterative methods come into play. The main benefit is that instead of working with a "full" matrix, which requires $O(n^2)$ operations to perform matrix-vector multiplication, in tridiagonal form matrix-vector multiplies cost only $O(n)$.

When working with a Toeplitz matrix, matrix-vector multiplication can be done in $O(n \ln n)$ time by embedding the $n \times n$ Toeplitz matrix in a $2n \times 2n$ circulant matrix, padding the vector with zeros and using FFT.

An approach of that kind preserves the Toeplitz structure of the original matrix, and so can be called a structure-preserving algorithm. Structure-preserving algorithms for bisymmetric eigenproblems have been studied, eg. Structure Preserving Algorithms for Perplectic Eigenproblems. We restrict ourselves for now to describing the "standard trick" mentioned in my comment for transforming a $2n \times 2n$ bisymmetric matrix into an orthogonally similar matrix with two $n \times n$ blocks on the diagonal.

Let $ \def\iddots{ {\kern3mu\raise1mu{.}\kern3mu\raise6mu{.}\kern3mu\raise12mu{.}}} P = \begin{pmatrix} 0 & \cdots & 1 \\ \vdots & \iddots & \vdots \\ 1 & \cdots & 0 \end{pmatrix}$ be the order-reversing $n \times n$ permutation matrix, clearly symmetric as well as orthogonal. Then define $U = \frac{1}{\sqrt{2}}\begin{pmatrix} I & P \\ -P & I \end{pmatrix}$, an orthogonal $2n \times 2n$ matrix.

The bisymmetric $2n \times 2n$ matrix $A$ has the form $\begin{pmatrix} M & B \\ B^T & PMP \end{pmatrix}$, where $M$ is symmetric and also $PB = B^T P$ is symmetric. Then:

$$ U^T A U = \begin{pmatrix} M - BP & 0 \\ 0 & PMP + PB \end{pmatrix} $$

Thus diagonalizing $A$ amounts to diagonalizing each of the half-sized symmetric blocks of this reduced form.


Below are some computations of eigenvalues for small sizes, showing the interlaced nature of the eigenvalues with incrementing $n$:

    n=6        n=7        n=8        n=9        n=10

                        3.512377              1.559856
             3.223818              1.361472  
  2.960929              1.142162              0.604773
             0.930378              0.414335  
  0.620470              0.205781             -0.024785
             0.005202             -0.203630  
 -0.278546             -0.396355             -0.455340
            -0.666005             -0.619805  
 -0.824663             -0.792701             -0.776527
            -0.949686             -0.922321  
 -1.149049             -1.069249             -1.010681
            -1.184892             -1.134022  
 -1.329141             -1.249268             -1.181594
            -1.358814             -1.277188  
                       -1.352748             -1.296923
  • $\begingroup$ Thanks! Anyway; if I understand correctly, this means that I have to give up on a closed-form solution, right? $\endgroup$ – Alessandro Gadaleta Jan 17 '13 at 9:27
  • $\begingroup$ @AlessandroGadaleta: I'm not certain that no closed-form solution exists, but it may be hard to find. I'll compute the eigenvalues (diagonal entries) for some smallish cases, say n = 6,8,10, and we can see if a pattern appears. Since the matrix "grows" by adding rows and columns at the end (bordering), theory suggests the eigenvalues for case n will interlace the eigenvalues for n+1. $\endgroup$ – hardmath Jan 17 '13 at 11:58
  • 1
    $\begingroup$ @AlessandroGadaleta: Take a look and see if the computed eigenvalues suggest a pattern related to your application. For example, it seems that the count of negative eigenvalues is roughly twice the count of positive eigenvalues. The largest (positive) eigenvalue will grow slowly to $+\infty$ like the harmonic series from which your matrix entries are drawn. $\endgroup$ – hardmath Jan 17 '13 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.