Skip to main content
1 of 2
Dustin G. Mixon
  • 7.6k
  • 2
  • 31
  • 56

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.

Dustin G. Mixon
  • 7.6k
  • 2
  • 31
  • 56