3
$\begingroup$

I'm interested in considering digraphs from an algebraic perspective, which leads me to the following question.

Consider an invertible 0-1 matrix of shape $n \times n$.

  • What lower and upper bounds are known about its singular values?
  • Are there any known results for the upper-triangular 0-1 special case, at least?

N.B. This question is cross-posted from Math.SE (where it won me the coveted Tumbleweed Badge).

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ I'm not a specialist in matrix theory, so this may be wrong: would Smith Normal Form help? Many of the manipulations to get SNF are done by triangular matrices with determinant one. If so, check out Miodrag Zivkovic and his 2005 ArXiv submission on classification of small 0-1 matrices. The values in the SNF depend greatly on the prime factorization of the determinant. Gerhard "It Is A Personal Favorite" Paseman, 2018.12.04 $\endgroup$
    – Gerhard Paseman
    Commented Dec 4, 2018 at 17:59
  • 1
    $\begingroup$ If you want to get something effortlessly, then looking at the Hilbert-Schmidt norm is usually a reasonable idea, and under your assumptions, this gives that $n\le \sum s_j^2 \le n(n-1)$. $\endgroup$
    – Christian Remling
    Commented Dec 5, 2018 at 0:39
  • $\begingroup$ @ChristianRemling: That's a nice idea for obtaining an tighter upper bound on the largest singular value (while leaving the question of a lower bound on the smallest singular value open). I think that we instead have $n \leqslant \sum s_j^2 \leqslant n^2 - (n-1)$, as the matrix $\bigl[\begin{smallmatrix} 1 & 1 \\ 0 & 1 \end{smallmatrix}\bigr]$ seems to violate your upper bound. $\endgroup$
    – Niel de Beaudrap
    Commented Dec 5, 2018 at 10:30
  • $\begingroup$ No. SNF results in A=PNQ where P and Q are integer matrices with determinants of absolute value 1, and N is diagonal with each nonzero element dividing the next. For A with absolute determinant value a prime p, the SNF N is the identity except for the lower right entry which is p. Gerhard "Sounds Quite Singular To Me" Paseman, 2018.12.05. $\endgroup$
    – Gerhard Paseman
    Commented Dec 5, 2018 at 15:48
  • $\begingroup$ @NieldeBeaudrap: Yes, your upper bound is correct (not mine), and in fact the observation I had in mind was that the matrix has to have at least $n-1$ zeros (or else two columns will be identical), which your bound expresses. $\endgroup$
    – Christian Remling
    Commented Dec 5, 2018 at 16:55

2 Answers 2

Reset to default
1
$\begingroup$

Obviously the maximum singular value is at most $n$. Moreover, for $n>1$ it is possible for $n-1$ to be a singular value (consider a matrix with diagonal entries $0$ and off-diagonal entries $1$), so this upper bound is not far from optimal.

The determinant of your matrix is an integer, so the product of singular values is at least $1$. Since the maximum singular value is at most $n$, the minimum singular value is at least $n^{-(n+1)}$. However, I don't expect that lower bound to be anywhere near optimal.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Let $J_n$ be the $n \times n$ matrix of all $1$s, and $M_n = J_n - I_n$. As you say, the largest singular value of $M_n$ is $n-1$; all of the others are $1$. We can push this a bit further with $X_n = J_n - I_n + E_{1,1}$, which (it seems to me) has a largest singular value of $\tfrac{1}{2}(\sqrt{(n-1)^2 + 4\,} + (n - 1))$. What is striking after some numerical experimentation is that, for $1 < n < 20$, the singular values apart from the largest and the smallest all seem to be 1, so that the smallest is the reciprocal of the largest in this case. Do you suppose that this somehow generalises? $\endgroup$
    – Niel de Beaudrap
    Commented Dec 5, 2018 at 10:59
  • $\begingroup$ Indeed, it's easy to see that $X_n$ has eigenvectors $e_i - e_{i+1}$ for eigenvalue $1$ for $i = 2 .. n-1$, so $1$ is an eigenvalue of multiplicity $n-2$. The determinant being $(-1)^{n+1}$ and trace being $1$ determines the other two eigenvalues. Since this is a hermitian matrix, the singular values are the absolute values of the eigenvalues, and the smallest is the reciprocal of the largest. $\endgroup$
    – Robert Israel
    Commented Dec 5, 2018 at 14:44
  • $\begingroup$ That's a helpful observation, and good to have confirmed. However, I was considering how in this extreme case, where we are making the largest singular value essentially as large as possible, we have $s_n \in \Omega(1/n)$ --- specifically in this case because $s_n = 1/s_1$ for $s_1 = \sqrt{n^2 - O(n)}$. What I wonder is whether it is plausible this feature of this case generalises, allowing us to see that $s_n \in \Omega(1/n)$, or possibly $s_n \in \Omega(1/n^{1+c})$ for some particular small constant $c$? $\endgroup$
    – Niel de Beaudrap
    Commented Dec 5, 2018 at 15:18
0
$\begingroup$

Take a look at "Spectra of Digraphs" by Richard A. Brualdi https://www.sciencedirect.com/science/article/pii/S0024379509001232, although I do not think that there is anything relating to invertibility specifically in there.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .