1
$\begingroup$

I am interested to know what kind of characterizations are known of the rank of bipartite graphs $G(n,m)$ ($n$ vertices on one side, $m$ on the other, $n \leq m$).

When is the incidence matrix full rank (rows indexed by one coclique, columns indexed by the other)? What are some conditions that guarantee full rank? Thank you.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ The incidence matrix ($B$ in Ken W. Smith's answer, below) is an arbitrary $(0,1)$-matrix. That is, any matrix with entries of $0$ or $1$ is the incidence matrix of a bipartite graph. It seems difficult to say much about matrices in such generality. If you are only looking for a sufficient condition, then how about something like: if the bipartite graph has an odd number of complete perfect matchings then the incidence matrix has full rank. But this is pretty naive. $\endgroup$
    – Zach Teitler
    Commented Mar 14, 2017 at 18:30
  • $\begingroup$ Yes, I am looking for sufficient conditions. I did know that naive condition, it is easily seen by expanding the determinant. $\endgroup$
    – user3399994
    Commented Mar 14, 2017 at 23:43
  • 1
    $\begingroup$ Note that "incidence matrix" is also used for the $V(G) \times E(G)$ matrix with $1$'s where $v \in e$. Both "bipartite adjacency matrix" and "biadjacency matrix" are terms I've heard used for your matrix. $\endgroup$
    – Ben Barber
    Commented Mar 15, 2017 at 10:58

2 Answers 2

Reset to default
1
$\begingroup$

Order the vertices $v_1,v_2...,v_m, w_1,w_2 ..., w_n$ where $v_i$ are vertices from one coclique and $w_j$ are vertices from the other. Assume $n \ge m$. The adjacency matrix is then $A=\begin{pmatrix} 0 & B\\ B^T & 0 \end{pmatrix}.$ Then $A^2=\begin{pmatrix} BB^T & 0 \\ 0 & B^TB\end{pmatrix}.$ This is singular if $n > m$, that is, if $B$ is not square. It is also singular if $B$ is a singular square matrix. So if $A$ is full rank then $B$ needs to be square and full rank so I think your question can be translated into one about the singularity of $B$. Since $B$ is then a square $(0,1)$-matrix, this becomes a fairly general question....

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, Ken. I guess I had in mind the incidence matrix; rows indexed by one coclique and columns indexed by the other. I edited the question $\endgroup$
    – user3399994
    Commented Mar 14, 2017 at 15:05
1
$\begingroup$

I don't know about full rank but a nice lower bound on the rank is given in the following paper:

N. Alon, H. T. Hall, C. Knauer, R. Pinchasi and R. Yuster, On graphs and algebraic graphs that do not contain cycles of length 4, J. Graph Theory 68 (2011), 91-102.

There is a preprint version.

Let $G$ be a bipartite graph with $m$ and $n$ vertices in its partitions. Let $E$ be the number of edges and let $s(G)$ be the number of $4$-cycles in $G$.

Also, denote by $\rho(G)$ the following regularity measure: $$ \rho(G)=\frac{4E^2}{n\sum{d_i^2}}, $$ where the $d_{i}$s are the vertex degrees.

Also, for a symmetric real matrix $M$ denote by $\rho(M)$ the following measure of the regularity of $M$'s spectrum: $$ \rho(M)=\frac{trace(A)^2}{n \cdot trace(A^2)}. $$

Then Theorem 6 in the above paper states that: $$ rank(A) \geq \rho(AA^T)m, $$ and $$ \rho(AA^T)=\frac{E^2}{4E^2/(\rho(G)(m+n))-E+4s(G)}. $$

Improve this answer
$\endgroup$

You must log in to answer this question.

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