グラフ$G=(V, E)$は$|V|\times |V|$の行列で表すことができます．この行列を${\bf A}$とした時，${\bf A}_{ij}$を頂点$i$と$j$を接続するエッジの重みとした行列を隣接行列 (Adjacency Matrix) と呼びます．

ところで，同一の集合内の頂点を接続するようなエッジが存在しないようにグラフの頂点集合を2集合に分割できるようなグラフを二部グラフ (Bipartite Graph) と呼びます．

この図のグラフは，赤い集合，青い集合それぞれの要素である頂点同士を接続するエッジが無いので二部グラフです．赤い線で囲まれた頂点集合を$V_{\rm red}$，青い線で囲まれた頂点集合を$V_{\rm blue}$と呼びます．また，このように隣接する頂点が存在しない頂点集合を「独立集合」と呼ぶことにします．

当然ですが，二部グラフも隣接行列を用いて表すことができます．図の二部グラフを隣接行列で表すと

{\bf A} =
\begin{bmatrix}
0 & 0 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0\\
1 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 1 & 1\\
0 & 0 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0\\
\end{bmatrix}

この行列は十分に疎なので，それを利用して省メモリに持つことも可能なのですが，今回は二部グラフの性質を利用してみます．

グラフにおいて重要なのは，頂点の接続情報です．よって，一般に頂点番号は自由に入れ替えてしまって構いません．このことを利用して，頂点番号を独立集合ごとにまとめてしまいます．

この図では，$V_{\rm blue}$側を若い番号でまとめましたが，逆でも構いません．この状態で隣接行列を書き出してみます．

{\bf A} =
\begin{bmatrix}
0 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 1\\
0 & 1 & 0 & 0 & 0 & 0\\
1 & 0 & 1 & 1 & 0 & 0\\
\end{bmatrix}

よく観察すると，${\bf O}_{n\times n}$を$n\times n$の零行列として，このような形で表現できることがわかります．

{\bf A} =
\begin{bmatrix}
{\bf O}_{|V_{\rm blue}|\times |V_{\rm blue}|} & {\bf B}_{|V_{\rm blue}|\times |V_{\rm red}|}\\
({\bf B}^T)_{|V_{\rm blue}|\times |V_{\rm red}|} & {\bf O}_{|V_{\rm red}|\times |V_{\rm red}|}\\
\end{bmatrix}

二部グラフにおいて，同一の独立集合内の頂点同士が接続されないことと，頂点番号を独立集合ごとにまとめたことにより，行と列それぞれが若い番号 (今回で言うと$|V_{\rm blue}|$以下の値)となる左上の部分と，それより大きい番号(今回で言うと$|V_{\rm blue}|$より大きい値)となる右下の部分がすべて0となります．
よって，二部グラフの接続情報は行列${\bf B}$にすべて集約することができ，$|V|\times |V|$の行列から$|V_{\rm blue}|\times |V_{\rm red}|$の行列で表せるようになりました．また，この${\bf B}$をBiadjacency Matrixと言います．(日本語訳するとしたら「二部隣接行列」？)

余談

Biadjacency Matrix という単語を聞いたことすらない上に，日本語記事もWikipedia くらいしか見つけられなかったので書いてみました．
実はNetworkXにライブラリがあったり，EcologicalNetworksにおける二部グラフはこの形式で扱う必要があるようです．
また，二部グラフのコミュニティ検知に関する論文で式変形などの際に用いられたりしているようです．

あと省メモリ目的なら疎行列であることを活かしてCSR形式などで持った方が良い気がします．(書いた後に気付きました)