Example for adjacency matrix of a bipartite graph

Solution 1:

When a (simple) graph is "bipartite" it means that the edges always have an endpoint in each one of the two "parts". So if the vertices are taken in order, first from one part and then from another, the adjacency matrix will have a block matrix form:

$$ A = \begin{pmatrix} 0 & B \\ B^T & 0 \end{pmatrix} $$

because the only nonzero entries correspond to edges between the first part and the second part, i.e. entries in the upper right hand block $B$ and its transpose in the lower left hand block.

So all the information about edges is given by block $B$, and provided the author is clear about this form of representation (which part is first, which is second), the adjacency matrix $A$ is reconstructable from $B$ as in the above formula.

Note that while the diagonal of $A$ is all zeros (as typical for an adjacency matrix), the entries in $B$ might all be ones (a so-called complete bipartite graph), or the zero entries in $B$ might appear to be randomly distributed.

For example, suppose we have the "utility graph", $K_{3,3}$, the complete bipartite graph with three nodes in each part. The biadjacency matrix is then all ones:

$$ B = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix} $$

and the $6\times 6$ adjacency matrix is:

$$ A = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 \end{pmatrix} $$