1
$\begingroup$

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?
$\endgroup$
11
  • 1
    $\begingroup$ 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. $\endgroup$
    – plshelp
    Sep 14 at 19:39
  • 2
    $\begingroup$ en.wikipedia.org/wiki/Matrix_multiplication $\endgroup$ Sep 14 at 20:22
  • 1
    $\begingroup$ $b_{ik}$ is the entry of $B$ on row $i$ and column $k$. $\endgroup$ Sep 14 at 20:22
  • 1
    $\begingroup$ $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$ $\endgroup$
    – nir shahar
    Sep 14 at 22:24
  • 1
    $\begingroup$ Well yes, thats what transposing a matrix does $\endgroup$
    – nir shahar
    Sep 15 at 10:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.