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
    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
    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
    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
    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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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