Is it bipartite?

Wolfram Language (Mathematica), 26 25 bytes

Tr[#//.x_:>#.#.Clip@x]<1&

Try it online!

How it works

Given an adjacency matrix A, we find the fixed point of starting with B=A and then replacing B by A²B, occasionally clipping values larger than 1 to 1. The k^th step of this process is equivalent up to the Clip to finding powers A^2k+1, in which the (i,j) entry counts the number of paths of length 2k+1 from vertex i to j; therefore the fixed point ends up having a nonzero (i,j) entry iff we can go from i to j in an odd number of steps.

In particular, the diagonal of the fixed point has nonzero entries only when a vertex can reach itself in an odd number of steps: if there's an odd cycle. So the trace of the fixed point is 0 if and only if the graph is bipartite.

Another 25-byte solution of this form is Tr[#O@n//.x_:>#.#.x]===0&, in case this gives anyone ideas about how to push the byte count even lower.

Previous efforts

I've tried a number of approaches to this answer before settling on this one.

26 bytes: matrix exponentials

N@Tr[#.MatrixExp[#.#]]==0&

Also relies on odd powers of the adjacency matrix. Since x*exp(x²) is x + x³ + x⁵/2! + x⁷/4! + ..., when x is a matrix A this has a positive term for every odd power of A, so it will also have zero trace iff A has an odd cycle. This solution is very slow for large matrices.

29 bytes: large odd power

Tr[#.##&@@#~Table~Tr[2#!]]<1&

For an n by n matrix A, finds A²ⁿ⁺¹ and then does the diagonal check. Here, #~Table~Tr[2#!] generates 2n copies of the n by n input matrix, and #.##& @@ {a,b,c,d} unpacks to a.a.b.c.d, multiplying together 2n+1 copies of the matrix as a result.

53 bytes: Laplacian matrix

(e=Eigenvalues)[(d=DiagonalMatrix[Tr/@#])+#]==e[d-#]&

Uses an obscure result in spectral graph theory (Proposition 1.3.10 in this pdf).

Husk, 17 bytes

§V¤=ṁΣṠMSȯDfm¬ṀfΠ

Prints a positive integer if the graph is bipartite, 0 if not. Try it online!

Explanation

This is a brute force approach: iterate through all subsets S of vertices, and see whether all edges in the graph are between S and its complement.

§V¤=ṁΣṠMSȯDfm¬ṀfΠ  Implicit input: binary matrix M.
                Π  Cartesian product; result is X.
                   Elements of X are binary lists representing subsets of vertices.
                   If M contains an all-0 row, the corresponding vertex is never chosen,
                   but it is irrelevant anyway, since it has no neighbors.
                   All-1 rows do not occur, as the graph is simple.
      ṠM           For each list S in X:
              Ṁf   Filter each row of M by S, keeping the bits at the truthy indices of S,
        S  fm¬     then filter the result by the element-wise negation of S,
         ȯD        and concatenate the resulting matrix to itself.
                   Now we have, for each subset S, a matrix containing the edges
                   from S to its complement, twice.
§V                 1-based index of the first matrix
  ¤=               that equals M
    ṁΣ             by the sum of all rows, i.e. total number of 1s.
                   Implicitly print.

APL (Dyalog Extended), ¹⁶ 13 bytes

⍱1 1⍉∨.∧⍣2⍣≡⍨

Try it online!

^{-3 bytes thanks to @H.PWiz.}

Uses the algorithm from Misha Lavrov's top Mathematica answer: initialize A = B = M, left-multiply B twice to A and clamp it until it reaches the fixed point, and test if the diagonal entries are all zero.

The regular matrix product A+.×B counts the number of two-step paths from node m to node p passing through any intermediate node n. If we change the code to A∨.∧B, we instead get a boolean matrix indicating if there exists any two-step path from node m to node p. We don't need extra "clamping" operation that way.

How it works

⍱1 1⍉∨.∧⍣2⍣≡⍨  ⍝ Input: adjacency matrix M
          ⍣≡⍨  ⍝ Find the fixed point, with
               ⍝     Starting point A = Left arg B = M...
     ∨.∧⍣2     ⍝   Left-multiply (matmul) B twice to A
               ⍝   indicating existence of paths (boolean)
 1 1⍉          ⍝ Extract the main diagonal
⍱              ⍝ Test if all elements are zero