Tutorials › Graph Theory (Undergraduate) › Bipartite Adjacency Matrices In Block Form

Home  /  Tutorials  /  Adjacency and Laplacian Matrices

Adjacency and Laplacian Matrices · Tutorial 631 of 799

Bipartite Adjacency Matrices In Block Form

You will derive and use the block form of the adjacency matrix of a bipartite graph, including how its rectangular block records edges and degrees.

Intermediate 9 min read

What You'll Learn

  • Arrange a bipartition so the adjacency matrix has zero diagonal blocks.
  • Define the rectangular biadjacency block and state its dimensions.
  • Prove the block-form criterion in both directions.
  • Recover vertex degrees and the edge count from the rectangular block.
  • Track how vertex reorderings change the block.
  • Spot why an arbitrary vertex ordering can hide the block structure.

Why the Vertex Order Matters

An adjacency matrix records which pairs of vertices are adjacent, but its visible pattern depends on the order assigned to the vertices. For a bipartite graph, a useful order lists all vertices in one part first and all vertices in the other part second. With this order, the two diagonal blocks are zero: there are no edges within either part. The off-diagonal block records exactly which cross-part pairs are edges.

Throughout, graphs are finite and simple. For a graph \(G=(V,E)\) with a specified vertex order \(v_1,\ldots,v_n\), its adjacency matrix \(\mathbf{A}(G)\) has entry \(1\) in position \((i,j)\) when \(v_i v_j\in E\), and entry \(0\) otherwise. Since the graph is undirected, \(\mathbf{A}(G)\) is symmetric; since it has no loops, its diagonal entries are zero. A graph is bipartite if its vertices can be partitioned into sets \(X\) and \(Y\) so every edge has one endpoint in each part. Either part may be empty.

Definition: Given a bipartite graph with parts \(X\) and \(Y\), order the vertices by listing \(X\) first and \(Y\) second. Its biadjacency matrix \(B\) has rows indexed by \(X\) and columns indexed by \(Y\), with \(B_{xy}=1\) if \(xy\in E\), and \(B_{xy}=0\) otherwise. If \(p=|X|\) and \(q=|Y|\), then \(B\) is a \(p\)-by-\(q\) matrix.

The biadjacency matrix is also called the bipartite adjacency block. It is not the usual vertex-edge incidence matrix: its rows and columns correspond to vertices in opposite parts, not to vertices and edges. In the grouped vertex order, the full adjacency matrix is

$$ \mathbf{A}(G)= \begin{pmatrix} \mathbf{0}_{p\times p} & B\\ B^{T} & \mathbf{0}_{q\times q} \end{pmatrix}. $$

The upper-right block records edges from \(X\) to \(Y\). The lower-left block must be its transpose because adjacency is symmetric. The diagonal blocks are zero because no edge has both endpoints in \(X\), or both endpoints in \(Y\). Importantly, \(B\) need not be square: its dimensions are determined by the sizes of the two parts.

The Block-Form Criterion

Theorem: A graph is bipartite if and only if its vertices can be ordered so that its adjacency matrix has the form \(\begin{pmatrix}\mathbf{0}&B\\B^T&\mathbf{0}\end{pmatrix}\) for some rectangular matrix \(B\) with entries \(0\) or \(1\).

Proof. Suppose first that \(G\) is bipartite with parts \(X\) and \(Y\). Put the vertices of \(X\) first and those of \(Y\) second. There are no edges within \(X\) or within \(Y\), so both diagonal blocks are zero. For \(x\in X\) and \(y\in Y\), the corresponding upper-right entry is \(1\) exactly when \(xy\in E\). The lower-left block records the same adjacencies with row and column indices reversed, so it is \(B^T\). This gives the stated form.

Conversely, suppose there is a vertex order in which the adjacency matrix has the stated form, with the first \(p\) vertices indexing the first block and the remaining \(q\) vertices indexing the second. The zero first diagonal block says that no two vertices in the first group are adjacent. The zero second diagonal block says the same for the second group. Every edge therefore joins the two groups, which form a bipartition. This argument also covers \(p=0\) or \(q=0\): the graph then has no edges and is bipartite. \(\square\)

This criterion concerns whether some ordering has the block form. An arbitrary ordering need not display it. Once the parts are fixed, changing the order within \(X\) permutes the rows of \(B\), and changing the order within \(Y\) permutes its columns. Swapping the names of the two parts replaces \(B\) by \(B^T\). The graph encoded by the block is unchanged.

Proposition: For a bipartite graph with biadjacency matrix \(B\), the sum of row \(x\) of \(B\) is \(\deg(x)\) for \(x\in X\), and the sum of column \(y\) of \(B\) is \(\deg(y)\) for \(y\in Y\). In particular, the number of edges is the sum of all entries of \(B\).

Proof. Fix \(x\in X\). Each entry in row \(x\) is \(1\) exactly when the corresponding vertex \(y\in Y\) is adjacent to \(x\). These are all the possible neighbors of \(x\), since no vertex of \(X\) is adjacent to \(x\). Thus the row sum counts precisely \(\deg(x)\). For a fixed \(y\in Y\), the entries equal to \(1\) in column \(y\) correspond exactly to its neighbors in \(X\), so the column sum is \(\deg(y)\). Finally, every edge has exactly one endpoint in \(X\), and therefore contributes exactly one \(1\) to one row of \(B\). Summing all entries counts each edge once and no non-edge, giving \(|E|\). If either part is empty, there are no edges and the sum over the empty set of entries is \(0=|E|\). \(\square\)

Reading the Block Form in Examples

Worked Example: The Complete Bipartite Graph \(K_{2,3}\)

Let \(X=\{u_1,u_2\}\), \(Y=\{v_1,v_2,v_3\}\), and let \(E\) contain all six cross-part edges: \(u_1v_1,u_1v_2,u_1v_3,u_2v_1,u_2v_2,u_2v_3\). There are no other edges. Order the vertices \(u_1,u_2,v_1,v_2,v_3\).

Each vertex in \(X\) is adjacent to all three vertices in \(Y\), so each row of \(B\) is \((1,1,1)\). Hence \(B\) is \(2\)-by-\(3\), and the full adjacency matrix is

$$ B=\begin{pmatrix}1&1&1\\1&1&1\end{pmatrix}, \qquad \mathbf{A}(G)= \begin{pmatrix} 0&0&1&1&1\\ 0&0&1&1&1\\ 1&1&0&0&0\\ 1&1&0&0&0\\ 1&1&0&0&0 \end{pmatrix}. $$

Check: Each row of \(B\) sums to \(1+1+1=3\), so \(\deg(u_1)=\deg(u_2)=3\). Each column sums to \(1+1=2\), so each \(v_j\) has degree \(2\). The sum of the entries of \(B\) is \(6\), matching the six edges listed in \(E\). Independently, the degree sum is \(2\cdot3+3\cdot2=12\), and each edge contributes two to that sum, giving \(12/2=6\) edges.

Worked Example: The Path \(P_5\)

Let \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45\}\). A bipartition is \(X=\{1,3,5\}\) and \(Y=\{2,4\}\), because each listed edge joins an odd-numbered vertex to an even-numbered one. Use the grouped order \(1,3,5,2,4\).

Vertex \(1\) is adjacent to \(2\) but not \(4\), so its row in \(B\) is \((1,0)\). Vertex \(3\) is adjacent to both \(2\) and \(4\), giving \((1,1)\). Vertex \(5\) is adjacent to \(4\) but not \(2\), giving \((0,1)\). Thus

$$ B=\begin{pmatrix}1&0\\1&1\\0&1\end{pmatrix}, \qquad \mathbf{A}(G)= \begin{pmatrix} 0&0&0&1&0\\ 0&0&0&1&1\\ 0&0&0&0&1\\ 1&1&0&0&0\\ 0&1&1&0&0 \end{pmatrix}. $$

Check: The row sums are \(1,2,1\), giving degrees \(1,2,1\) for vertices \(1,3,5\). The column sums are \(2,2\), giving degrees \(2,2\) for vertices \(2,4\). The sum of the entries of \(B\) is \(1+0+1+1+0+1=4\), equal to \(|E|=4\). Directly, the edge list contains \(12,23,34,45\), also four edges.

Worked Example: An Isolated Vertex in a Disconnected Graph

Let \(V=\{a,b,c,d,e\}\) and \(E=\{ab,cd\}\). The vertex \(e\) is isolated. Choose \(X=\{a,c,e\}\) and \(Y=\{b,d\}\), and order the vertices \(a,c,e,b,d\). The graph has two components containing edges and one isolated vertex; all edges still cross the chosen parts.

The edge \(ab\) gives a \(1\) in row \(a\), column \(b\), and \(cd\) gives a \(1\) in row \(c\), column \(d\). There are no other edges, so row \(e\) is zero:

$$ B=\begin{pmatrix}1&0\\0&1\\0&0\end{pmatrix}, \qquad \mathbf{A}(G)= \begin{pmatrix} 0&0&0&1&0\\ 0&0&0&0&1\\ 0&0&0&0&0\\ 1&0&0&0&0\\ 0&1&0&0&0 \end{pmatrix}. $$

Check: The row sums \(1,1,0\) give degrees \(1,1,0\) for \(a,c,e\), and the column sums \(1,1\) give degree \(1\) for each of \(b,d\). The entries of \(B\) sum to \(1+0+0+1+0+0=2\), matching the two edges in \(E\). The isolated vertex causes a zero row, not a failure of the block form.

Common Pitfall: Trusting the Current Order

A bipartite graph can have an adjacency matrix with nonzero entries inside the apparent diagonal blocks if the vertices have not been grouped by a bipartition. For a concrete example, let \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41\}\), a 4-cycle. In the order \(1,2,3,4\), the adjacency matrix is

$$ \begin{pmatrix} 0&1&0&1\\ 1&0&1&0\\ 0&1&0&1\\ 1&0&1&0 \end{pmatrix}. $$

If one incorrectly treats the first two vertices as one part and the last two as the other, the entries for edges \(12\) and \(34\) lie within the supposed parts. The mistake is not that the graph is non-bipartite; it is that this grouping is not a bipartition. Take \(X=\{1,3\}\) and \(Y=\{2,4\}\), and reorder as \(1,3,2,4\). The matrix becomes

$$ \begin{pmatrix} 0&0&1&1\\ 0&0&1&1\\ 1&1&0&0\\ 1&1&0&0 \end{pmatrix} = \begin{pmatrix} \mathbf{0}_{2\times2}&B\\ B^T&\mathbf{0}_{2\times2} \end{pmatrix}, \qquad B=\begin{pmatrix}1&1\\1&1\end{pmatrix}. $$

Here the block form is visible because the vertices have been ordered by the actual parts. The test is whether a suitable ordering exists, not whether the matrix in an arbitrary order already has zero diagonal blocks.

This representation is useful because it separates the structure of a bipartite graph into two vertex sets and a rectangular record of their cross-part adjacencies. The block dimensions immediately show the sizes of the parts, while the row and column sums provide degrees and the total number of \(1\)s gives the edge count. When constructing the matrix, first specify the two parts, then fix the order within each part, and finally fill in \(B\) from the edge set. This makes it less likely to confuse a missing edge with a vertex-ordering issue.

Check Your Understanding

For each question, state the vertex order or part assignment you use, and check any matrix entries against the specified edges.

  1. Let \(X=\{a,c\}\), \(Y=\{b,d,e\}\), and \(E=\{ab,ad,ce\}\). Write \(B\) in the row order \(a,c\) and column order \(b,d,e\), then give its dimensions.
  2. For a bipartite graph with parts of sizes \(4\) and \(2\), what are the dimensions of \(B\) and of the two zero diagonal blocks in the full adjacency matrix?
  3. Prove directly from the definition of \(B\) that a zero row corresponds to an isolated vertex in \(X\).
  4. Can a bipartite graph have an adjacency matrix that is not in block form in a particular vertex order? Explain using the 4-cycle above.
  5. If \(B\) has \(7\) entries equal to \(1\), how many edges does the graph have? Give the reason, not only the number.

Previous

Next

Back to Tutorials