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.

$\endgroup$
  • 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 Mar 14 '17 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 Mar 14 '17 at 23:43
  • $\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 Mar 15 '17 at 10:58
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....

$\endgroup$
  • $\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 Mar 14 '17 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)}. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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