# How to diagonalize this matrix?

Consider the $n\times m$ matrix $M=[M_1, \ldots, M_m]$ where the $i$-th column reads

$$M_i= \,^t(\underbrace{1,\ldots,1}_{a_i},0,\ldots,0)$$ where the $a_i$'s are given positive natural numbers.

Is it possible to compute the singular values of $M$ in terms of the $a_i$'s ?

Maybe it is simpler if one choose the $a_i$'s non-decreasing.

I am interested in this problem since it somehow generalize the case where $n=m$ and $a_i=n$ for all $i=1,\ldots,n$, and for which the singular values are $0$ with multiplicity $n-1$ and $n^2$ with multiplicity $1$. This comes from an easy kernel size plus trace argument. And I was wondering if it could be applied to this general case, but I didn't succeed ...

-
To start you're going to need $n = m$ to have eigenvalues or to talk about diagonalizing. –  Jim Feb 22 '13 at 18:49
Just to make sure I understand it correctly, you allow some of the $a_{i}$ to be zero? –  Andreas Caranti Feb 22 '13 at 18:50
The rank of such a matrix can be found by inspection. Is that enough of a generalization of the all 1s case? –  hardmath Feb 22 '13 at 19:09
@polkjh Permutation changes eigenvalues. Otherwise the determinant is always preserved. Yet some permutation matrices have determinant -1. –  user1551 Feb 22 '13 at 19:20
Perhaps it's an artifact of the revised wording about singular values, but the "all-ones" matrix has a non-zero singular value of $n$, not $n^2$. –  hardmath Feb 24 '13 at 13:25

## 1 Answer

Since we are now asking about singular values, arranging the columns for non-decreasing $a_i$ is without loss of generality. A permutation of columns does not affect a matrix's singular values.

Consider $A = M'M$, a symmetric positive semi-definite matrix, whose eigenvalues are squares of the singular values of $M$. $A$ is a structured matrix with $A_{ij} = \min \{a_i,a_j\} = a_{\min \{i,j\} }$.

The nonsingular case ($n \times n$ matrix, strictly increasing $a_i = i$) is included in a "test case gallery" as minij in MatLab and other suites. According to comments in this test C code, the eigenvalues of $A$ have an explicit formula:

$$\frac{0.5}{ 1 - \cos \left( \frac{( 2k - 1 )\pi}{ 2n + 1 } \right) } \;\; \forall \; 1 \le k \le n$$

Accordingly the singular values of $M$ should be the respective square roots of those. For $n=2$ we get singular values $\varphi = 1.61803\ldots$ and $\varphi - 1 = 0.61803\ldots$ as a perhaps lucky connection to the golden ratio.

A similarly simple expression for singular values of the singular cases seems a daunting challenge, if only because of the large number of possibilities. However the rank of $M$ (resp. of $A$) can be found by counting the number of columns containing a "leading one", since removing duplicate rows puts $M$ in row-echelon form (due to column sorting). Therefore the nullity (dimension of nullspace) of $M$ is easily found, or in other words the count of singular values which are zero.

-