# Matrix of a graph and computational complexity

Given a simple undirected graph with no self-loops, $$G = (V,E)$$, where $$V = {1,2,...,n}$$, an $$n × n$$ matrix $$A$$ is said to be the adjacency matrix of $$G$$ if $$A_{i,j}$$ is $$1$$ if $$(i, j) ∈ E$$ and $$0$$ otherwise. Now, suppose we define a special kind of matrix product for matrices whose entries are only 0 or 1. In this special matrix product we replace addition by OR and multiplication by AND. With this being our definition of the matrix product answer the following questions:

1. If $$B_2 = (A+I)^2$$ then argue that $$B_2 = C_2 +I$$ where $$C_2$$ is the adjacency matrix of the graph $$G′ = (V,E′)$$ with the same vertex set as $$G$$. We say that $$(i,j) ∈ E′$$ if $$(i,j) ∈ E$$ or there exists a $$k ∈ V$$ such that $$(i,k),(k,j) ∈ E$$.

2. Is it possible to compute $$C_2$$ (by some other way perhaps) in time which is $$o(n^2)$$? Or is there some example on which the time taken to compute $$C_2$$ has to be $$Ω(n^2)$$? Cause I think that in this case the time taken would be $$θ(n^2)$$

I tried manipulating $$B_2$$ and then applying the new matrix product properties, but I wasn't able to give a concrete argument about $$C_2$$. As far as the complexity goes, I have no idea on how to go about with it. Any help is appreciated. Thanks!

• The standard matrix multiplication takes $O(n^3)$ time. Do you actually mean $o(n^3)$ time? Another way to obtain the adjacency matrix of $G'$ is just using the standard matrix product of A and itself, but replacing its non-zero entries with 1. Nov 16, 2018 at 16:19

Let $$B_1 = I + A$$. Then $$B_1(i,j) = 1$$ iff $$d(i,j) \leq 1$$, where $$d(i,j)$$ is the distance between $$i$$ and $$j$$ in the graph. Now $$B_2 = B_1^2$$, and so by definition, $$(B_2)_{ij} = \bigvee_k (B_1)_{ik} \land (B_1)_{kj}.$$ In words, $$(B_2)_{ij} = 1$$ iff there exists a vertex $$k$$ such that $$(B_1)_{ik} = (B_1)_{kj} = 1$$, i.e. $$d(i,k) \leq 1$$ and $$d(k,j) \leq 1$$.
We can now prove that $$(B_2)_{ij} = 1$$ iff $$d(i,j) \leq 2$$. Indeed, if $$(B_2)_{ij} = 1$$ then there exists $$k$$ such that $$d(i,k),d(k,j) \leq 1$$, and so $$d(i,j) \leq d(i,k) + d(k,j) \leq 2$$. Conversely, suppose that $$d(i,j) \leq 2$$. We consider two cases. If $$d(i,j) \leq 1$$ then $$k := j$$ satisfies $$d(i,k) \leq 1$$ and $$d(k,j) = 0 \leq 1$$, and so $$(B_2)_{ij} = 1$$. If $$d(i,j) = 2$$, choose a shortest path from $$i$$ to $$j$$, and let $$k$$ be the vertex in the middle. Then $$d(i,k) = d(k,j) = 1$$. In both cases, $$(B_2)_{ij} = 1$$.
You cannot compute $$C_2$$ faster than $$n^2$$, simply because it contains $$n^2$$ many entries. The asymptotically fastest way known to compute $$C_2$$ is by squaring $$I + A$$ (using the usual matrix multiplication), zeroing the diagonal, and replacing each entry larger than 1 with 1. This takes time $$O(n^\omega)$$, where $$\omega$$ is the matrix multiplication constant.