3
$\begingroup$

Let $\mathscr{M}[n,d]$ be collection of $n\times n$ symmetric matrices with real entries from $\{0,1\}$ such that every row/column is distinct with sum of every row/column being $d$.

What is minimum real rank of matrices in $\mathscr{M}[n,d]$?

Given real rank $r$, then $\mathscr{N}[r,d]$ be collection of symmetric rank $r$ square matrices with real entries from $\{0,1\}$ such that every row/column is distinct with sum of every row/column being $d$.

What is largest size of matrix in $\mathscr{N}[r,d]$?

Is there an algebraic or geometric way to describe these sets?

Improve this question
$\endgroup$
1
  • $\begingroup$ Not sure if this would help or not, but one can show (it is simply by using Cauchy Schwarz inequality with the non zero eigenvalues) that, if A is a n by n matrix then rank of A is at least ( (trace(A))^2 ) / trace(A^2), and for symmetric matrices the mentioned ratio of traces can be written in a compact way. $\endgroup$
    – Aditya Guha Roy
    Commented Oct 18, 2019 at 13:52

1 Answer 1

Reset to default
4
$\begingroup$

If you further assume that the diagonal of your matrices are all zeros, it's natural to view your matrices as adjacency matrices of graphs. With this identification, your sum condition means the graph is $d$-regular, and the distinct-row condition means the graph is reduced (see for example this paper).

In fact, that same paper considers a function $m(r)$, defined to be the number of vertices in the largest reduced graph of rank $r$. Note that upper bounds on $m(r)$ provide upper bounds for your second question. Kotlov and Lovasz's result in the beginning of section 4 gives that $m(r)=O(2^{r/2})$, and this is tight by Proposition 5.

Section 5 of the paper discusses how rank is related to other parameters of the graph (e.g., number of components, clique number, etc.), but the minimum/maximum degree does not appear to be considered.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Wouldn't the adjacency matrix of a graph also have zeros on the diagonal? $\endgroup$
    – François G. Dorais
    Commented Jun 28, 2015 at 12:58
  • 1
    $\begingroup$ Good point. I updated my answer accordingly. $\endgroup$
    – Dustin G. Mixon
    Commented Jun 28, 2015 at 13:09

You must log in to answer this question.

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