Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 8 down vote favorite
2

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 ...

share|improve this question
3  
To start you're going to need $n = m$ to have eigenvalues or to talk about diagonalizing. – Jim Feb 22 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 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 at 19:09
2  
@polkjh Permutation changes eigenvalues. Otherwise the determinant is always preserved. Yet some permutation matrices have determinant -1. – user1551 Feb 22 at 19:20
1  
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 at 13:25
show 8 more comments

1 Answer

up vote 2 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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