Problem on bipartite graphs. Let's $G$ is bipartite graph with sides $X=\{v_1,v_2,\ldots,v_n\}$ and $Y=\{u_1,u_2,\ldots,u_n\}.$ Let $|N_G(v_i)|=k$ and $|N_G(v_i)\cap N_G(v_j)|=d\lt k~,(i\ne j)$. Prove that $|N_G(u_i)|=k$ and $|N_G(u_i)\cap N_G(u_j)|=d,~(i\ne j)$. $N_G(v)$ is neighborhood of vertex $v$ in graph $G$.
I have no idea how I can start the proof.
 A: Let $A$ denote the adjacency matrix for the graph. We order the vertices in such a way that we may write
$$A = \begin{pmatrix} 0 & B\\B^\mathrm{T} & 0\end{pmatrix}$$
Note that a decomposition like this is possible for any bipartite graph. The matrix $B$ represents the incidences of $X$ in $Y$.  Note that by assumption of $|X|=|Y|=n$, the matrix $B$ is an $n\times n$ square matrix. Also note that $B$ is a $0$-$1$ matrix.
The conditions that $|N_G(v_i)|=k$ and $|N_G(v_i)\cap N_G(v_j)| = d<k$ now translate to 
$$\mathbf{b}_i\cdot \mathbf{b}_j = (k-d)\delta_{ij}+d$$
where $\mathbf{b}_i$ denotes the $i$th row of the matrix $B$. The above condition of course implies that 
$$BB^\mathrm{T} = (k-d)I_n + dJ_n\tag{*}$$
where $I_n$ is the identity matrix and $J_n$ is the matrix of all ones.
Lemma: A $0$-$1$ square matrix $B$ which satisfies ($*$) with $k>d$ is an invertible normal matrix.
Proof: The eigenvalues (up to multiplicity) of $J_n$ are $n$ and $0$, therefore the eigenvalues of $BB^\mathrm{T}$ are $k+(n-1)d$ and $k-d$. In particular, this means that $BB^\mathrm{T}$ is invertible and hence $B$ is also invertible.
Notice now that $B$ satisfies
$$BJ = kJ,\ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ J=kB^{-1}J$$
Right-multiplying $(*)$ by $J$ gives
$$BB^\mathrm{T}J = (k-d)J + dJ^2 = (k-d)J + ndJ = [k+(n-1)d]J$$
Applying $B^{-1}$ to the above, we get
$$B^\mathrm{T}J = [k+(n-1)d]B^{-1}J = \frac{k+(n-1)d}{k}J$$
Taking the transpose of the above, we get
$$JB = \frac{k+(n-1)d}{k}J$$
Right-multiplying by $J$ yields
$$JBJ = n\frac{k+(n-1)d}{k}J$$
On the other hand, we also know that $BJ = kJ$ so that
$$JBJ = nkJ$$
On comparison, we must have
$$k = \frac{k+(n-1)d}{k}$$
Therefore we get
$$JB = kJ = BJ$$
and consequently $B$ and $B^\mathrm{T}$ commutes with $BB^\mathrm{T}$. Therefore
$$B^\mathrm{T}B = B^\mathrm{T}(BB^\mathrm{T})(B^T)^{-1} = (BB^\mathrm{T})[B^\mathrm{T}(B^\mathrm{T})^{-1}] = BB^\mathrm{T}$$
as required. $\square$
Finally, note that 
$$B^\mathrm{T}B = (k-d)I_n + dJ_n$$
is precisely the condition required for $|N_G(u_i)| = k$ and $|N_G(u_i)\cap N_G(u_j)|=d$, which completes our proof. In addition, we have the following corollary as revealed by the proof.
Corollary: If $G$ satisfies the mentioned hypotheses, then $k^2 - k = (n-1)d$. $\square$
Note that the above corollary has a simple combinatorial interpretation. Fix an arbitrary vertex $v\in X$ and consider the number of ways we can reach some other vertex $v\neq v'\in X$ in $2$ steps. We count this in $2$ ways.
First, since $v$ has $k$ neighbors in $Y$, we may choose any of the $k$ neighbors. Each neighbor of $v$ also has $k$ neighbors, one of which is $v$ itself. Therefore we may reach some vertex $v'\in X$ in $k(k-1)$ ways.
Alternatively, each of the $n-1$ other vertices of $X$ shares a size $d$ neighborhood with $v$. Therefore each $v'\in X$ may be reached in precisely $d$ ways from $v$. The total number of ways from $v$ to some other $v'$ is therefore $d(n-1)$.
A: As I promised here is the solution.
Let's $A=(a_{ij})_{i,j=1}^n$ be the following matrix: $a_{ij}=1,$ if $\{v_i,u_j\}$ is edge of graph $G$ and $a_{ij}=0,$ otherwise. From the conditions it follows that $AA^T=dB+(k-d)I,$ where $B$ is a matrix with all entries equal $1$. It is easy to check (by finding determinant or by proving that columns independent) that $det(AA^T)\ne0,$ therefore $det(A)\ne0$. So we have $$A^TA=A^{-1}(AA^T)A=dA^{-1}BA+(k-d)I.$$ Now to complete the proof we need to prove that $A^{-1}BA=B,$ that is, $AB=BA$. Let $e^T=(1,1,\ldots,1)$, then $e$ is an eignvector for $A$ (therefore for $A^{-1}$ too) and also for $AA^T$. So $e$ is an eignvector for $A^{-1}(AA^T)=A^T$, $A^Te=k'e.$ As $k'n=e^TAe=kn$, $k'=k$. Therefore $eA=ke~\Rightarrow~BA=kB=AB.$  
