# Describing the matrix product $BB^T$ of the incidence matrix of a directed graph $G=\left< V,E \right>$

I would like to discuss a solution with you below please.

Describing the matrix product $$BB^T$$ of the incidence matrix of a directed graph $$G=\left< V,E \right>$$.

Question: The incidence matrix of a directed graph $$G=\langle V,E \rangle$$ with no self-loops is a $$|V| \times |E|$$ matrix $$B=(b_{ij})$$ such that,

$$b_{ij}=\begin{cases} 1& \text{if edge j enters vertex i,} \\ -1 & \text{if ege j leaves vertex i,} \\ 0 & \text{otherwise.} \end{cases}$$

Describe what the entries of the matrix product $$BB^T$$ represent, where $$B^T$$ is the transpose of $$B$$.

Solution: If the elements of $$B$$ are $$b_{ij}$$, then the elements of transpose $$B^T$$ is $$b_{ji}$$. Now, $$BB^T = \sum_{k \in E}{}(b_{ik}b_{jk}) \tag{1}\label{1}.$$

We then have two cases for $$i,j$$:

Case 1: if $$i=j$$, means the row in $$B$$ is multiplied by the column in $$B^T$$, so we got $$-1 \times -1$$ together, which produce positive integer. $$-1$$ means outgoing edge, and same thing when we have $$1 \times 1$$ means ingoing edges. So total of product gives $$\mathit{incoming}(i) + \mathit{outgoing}(i)$$ edges of vertex $$i$$.

Case 2: if $$i \ne j$$, etc.

Problem:

• Why in \ref{1} we have $$BB^T = \sum_{k \in E}{}(b_{ik}b_{jk})$$? I mean what $$b_{ik}$$ here means? I understand that $$k \in E$$ means $$k$$ in the set of edges of graph $$G=\langle V, E \rangle$$. If we multiply the vectors from a matrix to its transpose, we will get $$b_{ij} \times b_{ji}$$, so I am not sure why it's written in this form $$(b_{ik}b_{jk})$$ please?
• Shouldn't it be $k\in V$ because $b_{ij}$ indices are $i,j \in V = \{1,2,3,...,n\}$? It's probably a typo in your source. Sep 14 at 19:39
• en.wikipedia.org/wiki/Matrix_multiplication Sep 14 at 20:22
• $b_{ik}$ is the entry of $B$ on row $i$ and column $k$. Sep 14 at 20:22
• $B_{jk}=B^T_{kj}$. So what is written is equivalent to $\sum_{k} B_{ik}B^T_{kj}$, which is exactly the definition of matrix multiplication between $B$ and $B^T$ Sep 14 at 22:24
• Well yes, thats what transposing a matrix does Sep 15 at 10:03