I was reading this chapter and I came to one thing that seems easy but I cannot prove. What is the adjacency matrix of a strong graph product?
Below I copied the part of the chapter that I am refering to with the formula $$((A_\Gamma+I) \otimes (A_\Delta+I))−I$$
Given graphs $\Gamma$ and $\Delta$ with vertex sets $V$ and $W$, respectively, their strong product $\Gamma \boxtimes \Delta$ is the graph with vertex set $V \times W$, where two distinct vertices $(v,w)$ and $(v',w')$ are adjacent whenever $v$ and $v'$ are equal or adjacent in $\Gamma$ , and $w$ and $w'$ are equal or adjacent in $\Delta$. If $A_\Gamma$ and $A_\Delta$ are the adjacency matrices of $\Gamma$ and $\Delta$, then $$((A_\Gamma+I)⊗(A_\Delta+I))−I$$ is the adjacency matrix of $\Gamma \boxtimes \Delta$.
Any hints are welcome.
Here, $A \otimes B$ denotes the Kronecker product (Wikipedia link) of two matrices. The basic idea can be demonstrated with the $2 \times 2$ example $$\begin{bmatrix}a_{11} & a_{12} \\ a_{21} & a_{22}\end{bmatrix} \otimes \begin{bmatrix}b_{11} & b_{12} \\ b_{21} & b_{22}\end{bmatrix} = \begin{bmatrix}a_{11}\begin{bmatrix}b_{11} & b_{12} \\ b_{21} & b_{22}\end{bmatrix} & a_{12}\begin{bmatrix}b_{11} & b_{12} \\ b_{21} & b_{22}\end{bmatrix} \\ a_{21}\begin{bmatrix}b_{11} & b_{12} \\ b_{21} & b_{22}\end{bmatrix} & a_{22}\begin{bmatrix}b_{11} & b_{12} \\ b_{21} & b_{22}\end{bmatrix}\end{bmatrix} = \begin{bmatrix} a_{11} b_{11} & a_{11} b_{12} & a_{12} b_{11} & a_{12} b_{12} \\ a_{11} b_{21} & a_{11} b_{22} & a_{12} b_{21} & a_{12} b_{22} \\ a_{21} b_{11} & a_{21} b_{12} & a_{22} b_{11} & a_{22} b_{12} \\ a_{21} b_{21} & a_{21} b_{22} & a_{22} b_{21} & a_{22} b_{22} \end{bmatrix}$$ and you can see Wikipedia for a general example.
The idea is that it makes sense to index the rows and columns of $A \otimes B$ not with single numbers $i$ and $j$ but with pairs $(i_1, i_2)$ and $(j_1, j_2)$, which are then sorted lexicographically: $$(1,1) < (1,2) < (2,1) < (22)$$ in the example above, and $$(1,1) < (1,2) < \dots < (1,n_2) < (2,1) < \dots < (2,n_2) < \dots < \dots < (n_1,1) < \dots < (n_1,n_2)$$ in general.
Then we can define the Kronecker product entry-by-entry as $$(A \times B)_{(i_1, i_2), (j_1,j_2)} = A_{i_1, j_1} B_{i_2, j_2}.$$
By itself, the Kronecker product would give us the weak product of two graphs: $A_\Gamma \otimes A_\Delta = A_{\Gamma \times \Delta}$. The reason is that we define $(A_\Gamma)_{v,w} = 1$ iff $v$ is adjacent to $w$ in $\Gamma$, and $(A_\Delta)_{v',w'} = 1$ iff $v'$ is adjacent to $w'$ in $\Delta$. Then we get$$(A_\Gamma \otimes A_\Delta)_{(v,v'), (w,w')} = (A_\Gamma)_{v,w} (A_\Delta)_{v',w'},$$ which is $1$ iff both $(A_\Gamma)_{v,w}$ and $(A_\Delta)_{v',w'}$ are $1$: if both $v$ and $w$ are adjacent and $v'$ and $w'$ are adjacent.
We use $A_\Gamma+I$ and $A_\Delta+I$ to compute with the strong product instead. You can think of $A_\Gamma+I$ as the "adjacency-or-equality" matrix of $\Gamma$: $(A_\Gamma+I)_{v,w} = 1$ iff $v$ is adjacent to $w$ or $v=w$. Equivalently, this is the adjacency matrix for the graph $Gamma'$ formed by adding loops at every vertex to $\Gamma$. The Kronecker product of $A_\Gamma+I$ and $A_\Delta+I$ will have a $1$ in the $((v,v'),(w,w'))$ entry if both $(A_\Gamma+I)_{v,w}$ and $(A_\Delta+I)_{v',w'}$ are $1$: if $v,w$ are ajacent or equal, and $v',w'$ are adjacent or equal.
This is almost the adjacency matrix of $\Gamma \boxtimes \Delta$. In fact, it's the "adjacency-or-equality" matrix of $\Gamma \boxtimes \Delta$: it also has a $1$ in the diagonal entries $((v,v'), (v,v'))$ because $v=v$ and $v'=v'$. We want the actual adjacency matrix, so we fix this by subtracting $I$, giving the formula $$(A_\Gamma + I) \otimes (A_\Delta + I) - I$$ that you wanted.