# STCON in L using matrix multipication algorithm?

I'm trying to understand why the following is incorrect.

Given a $STCON$ problem, specifically a graph and nodes $(G, s, t)$, we can assume we are given it's adjacency matrix, $A$. By adding self-loop (filling the main diagonal with $1$'s) we can multiple this matrix with itself n times, each time checking if the $s,t$ entry is $1$, and if so returning true.

We know multiplying binary matrices is in $L$ (need to "save" only couple of indices), and by also saving $n$ (number of total matrix multiplications) one can solve $STCON$ also in $L$.

Where am I wrong here?

For graph connectivity, the input is the adjacency matrix of the graph, along with the two vertices of interest, and the output is the single bit "yes" or "no". Your proposed algorithm requires remembering the matrix of paths you've discovered so far, which has size $n^2$, and that's not logarithmic.
• Quadratic space is not needed if each bit of the intermediate matrices is computed on demand. However, the space usage is still $\Omega((\lg n)^2)$. Jul 14, 2018 at 7:54