Let G as a bipartite graph. Show that the adjacency matrix of G can be written as in the picture given below (Actually I don't know how to make that matrix with the dashline like that, can you show me?), but if you ask me to make the matrix:
$\begin{bmatrix} O & P \\ Q & O \end{bmatrix}$
O, P, and Q are submatrices;
O is a submatrix whose entries are 0 (Zero).
P is a transpose matrix of Q.
I have learn about bipartite graph very well and understand about adjacency matrix, but the problem above seem hard for me to solve (Well, i am stuck)
Please help me. Thank you very much.
Best Answer
A bipartite graph has vertices in two sets $S_1$ (size $n$) and $S_2$ (size $m$), such that all vertices are either in $S_1$ or in $S_2$, and the vertices in $S_1$ are not connected to other vertices in $S_1$, and the vertices in $S_2$ are not connected to other vertices in $S_2$.
You can sort the vertices as follows $$\text{vertices}=\left\{\underbrace{v_1,\cdots,v_n}_{\in S_1},\underbrace{v_{n+1},\cdots,v_{n+m}}_{\in S_2}\right\}$$ Because the vertices in $S_1$ are not connected to other vertices in $S_1$, you know that the $(1,1)$ block in your adjacency matrix must be zero, and the same for your $(2,2)$ block.