Vrftsjtryk

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!