Rank adjacency matrix bipartite graph 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.
 A: 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....
A: 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)}.
$$
