A computer science problem by Thaddeus Abiy

Computer science answer:

$A=\begin{pmatrix} 0&1&0&0&1&1&0&0&0&0\\ 1&0&1&0&0&0&1&0&0&0\\ 0&1&0&1&0&0&0&1&0&0\\ 0&0&1&0&1&0&0&0&1&0\\ 1&0&0&1&0&0&0&0&0&1\\ 1&0&0&0&0&0&0&1&1&0\\ 0&1&0&0&0&0&0&0&1&1\\ 0&0&1&0&0&1&0&0&0&1\\ 0&0&0&1&0&1&1&0&0&0\\ 0&0&0&0&1&0&1&1&0&0\\ \end{pmatrix}$

$A^2=\begin{pmatrix} 3&0&1&1&0&0&1&1&1&1\\ 0&3&0&1&1&1&0&1&1&1\\ 1&0&3&0&1&1&1&0&1&1\\ 1&1&0&3&0&1&1&1&0&1\\ 0&1&1&0&3&1&1&1&1&0\\ 0&1&1&1&1&3&1&0&0&1\\ 1&0&1&1&1&1&3&1&0&0\\ 1&1&0&1&1&0&1&3&1&0\\ 1&1&1&0&1&0&0&1&3&1\\ 1&1&1&1&0&1&0&0&1&3\\ \end{pmatrix}$

$\frac{A^2+A-K}{2}=I_{10}$ which has det=1.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

A = [[0, 1, 0, 0, 1, 1, 0, 0, 0, 0], [1, 0, 1, 0, 0, 0, 1, 0, 0, 0], [0, 1, 0, 1, 0, 0, 0, 1, 0, 0], [0, 0, 1, 0, 1, 0, 0, 0, 1, 0], [1, 0, 0, 1, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 1, 1, 0], [0, 1, 0, 0, 0, 0, 0, 0, 1, 1], [0, 0, 1, 0, 0, 1, 0, 0, 0, 1], [0, 0, 0, 1, 0, 1, 1, 0, 0, 0], [0, 0, 0, 0, 1, 0, 1, 1, 0, 0]]
B = []

for i in xrange(10):
    B += [ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] ]
    for j in xrange(10):
        B[i][j] += A[i][j] - 1
        for k in xrange(10):
            B[i][j] += A[i][k] * A[k][j]

print "\n".join([str(line) for line in B])

Output:

[2, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 2, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 2, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 2, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 2, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 2, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 2, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 2, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 2]

Mathematics answer:

$A^2=(b_{ij})$ gives the number of path of length 2 from vertex $i$ to vertex $j$ , which is 3 if $i=j$ , 0 if vertices are neighbours and 1 if they're not. Then, $A+A^2$ gives the number of path of length 1 or 2 between vertices, which is 3 if the end vertex is the same as the starting one, and 1 in the other cases.

If $A = (a_{ij})$ is an adjacency matrix of an unordered graph, then $A^2 = (b_{ij})$ , where $b_{ij}$ is the number of adjacent vertices shared by vertex $i$ and $j$ . In the above graph, it is clearly visible that

• each vertex has three adjacent vertices, hence share all $3$ adjacent vertices with itself => $b_{ii} = 3$
• each vertex share $zero$ adjacent vertices with each of its adjacent vertices => $b_{ij} = 0$ , where $a_{ij} = 1$
• each vertex share $1$ adjacent vertex with all other vertices => $b_{ij} = 1$ , where $a_{ij} = 0$ and $i \neq j$

With simple observation, we see that $K - A$ will give something similar to $A^2$ . What's missing is that all the diagonal elements are 1 instead of 3 as desired. So final step, add $2I_{10}$ into that. Hence finally $A^2 = K - A + 2I$ or

$\frac {A^2 + A - K}{2} = I$

Ans : det $(I)$ = 1