It is not enough to check whether the $i,j$ entry of $A^{n-1}$ is equal to $1$; not every connected graph has a path of length $n-1$ between every two vertices. Also, you're wrong about what it means for every entry of $(I+A)^{n-1}$ to be non-zero.
Hint: use the binomial expansion
$$
(I+A)^{n-1} = \sum_{k=0}^{n-1} \binom{n-1}k A^k
$$
When a (simple) graph is "bipartite" it means that the edges always have an endpoint in each one of the two "parts". So if the vertices are taken in order, first from one part and then from another, the adjacency matrix will have a block matrix form:
$$ A = \begin{pmatrix} 0 & B \\ B^T & 0 \end{pmatrix} $$
because the only nonzero entries correspond to edges between the first part and the second part, i.e. entries in the upper right hand block $B$ and its transpose in the lower left hand block.
So all the information about edges is given by block $B$, and provided the author is clear about this form of representation (which part is first, which is second), the adjacency matrix $A$ is reconstructable from $B$ as in the above formula.
Note that while the diagonal of $A$ is all zeros (as typical for an adjacency matrix), the entries in $B$ might all be ones (a so-called complete bipartite graph), or the zero entries in $B$ might appear to be randomly distributed.
For example, suppose we have the "utility graph", $K_{3,3}$, the complete bipartite graph with three nodes in each part. The biadjacency matrix is then all ones:
$$ B = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix} $$
and the $6\times 6$ adjacency matrix is:
$$ A = \begin{pmatrix}
0 & 0 & 0 & 1 & 1 & 1 \\
0 & 0 & 0 & 1 & 1 & 1 \\
0 & 0 & 0 & 1 & 1 & 1 \\
1 & 1 & 1 & 0 & 0 & 0 \\
1 & 1 & 1 & 0 & 0 & 0 \\
1 & 1 & 1 & 0 & 0 & 0 \end{pmatrix} $$
Best Answer
You can use a quick algorithm to check whether it's bilateral.
You're given an adjacency matrix of order $2n$ (i.e. a representation of a graph with $2n$ vertices.)
Find the column with the most ones in it; suppose it's column $k$. Let $N_k$ be the list of ones in column $k$ (these are the neighbors of vertex $k$). Initialize a partition $P \equiv N_k$, and a partition $Q=\{k\}$.
[Loop.] Iterate over each column $j$ in the matrix:
If $P$ has more than $n$ ones in it, the graph can't be bipartite. In that case, quit and return NOT BIPARTITE.
Compute $N_j$. Now either:
Once again, if $P$ has more than $n$ members, the graph can't be bipartite—quit and return NOT BIPARTITE.
If the graph really is bipartite, $P$ now contains a complete partition of the graph. Permute the adjacency matrix to put all the members of $P$ first, and all of the members of $Q$ last.
If the matrix is now in the canonical form of a bipartite adjacency matrix (where the upper-left and lower-right blocks are all zero), the graph is bipartite; quit and return BIPARTITE. Otherwise, the graph isn't bipartite — quit and return NOT BIPARTITE.
Here's how to use this algorithm. Take your second graph as an example, which has $2n$ vertices with $n=3$.