Is the set of all cycles of length 4 is linearily independent in a graph? Consider all the cycles of length 4 in a graph which doesn't contain cycles of length less than 4 (and odd cycles either) and a matrix $A$ in which $a_{ij}=1$ if the $i$th 4-member cycle contains the $j$th edge, else $a_{ij}=0$. Are the rows of the matrix $A$ linearly independent?
 A: Consider the graph $C_8 \times C_8$.  Think of this as a chess board drawn on a torus by gluing the opposite sides of the board to one another, where the vertices are the corners of the squares and the edges are the edges of the squares.  
Now clearly the sum of the column vectors corresponding to the black squares is just the vector of all ones, since each edge is adjacent to one black square. But of course the same holds for the white squares, so the sum of the black squares equals the sum of the white squares and we have a linear dependency.
A: Let $C$ be the cycles of length $4$ in a graph. Per your definition, the cycles of length $4$ are linearly dependent if and only if there exists a nonzero function $f: C \to \mathbb{R}$ such that on every edge $e$ we have $\sum_{e \in C} f(C) = 0$. 
Then it becomes clear that Nate's answer is correct. In fact if you take the $5 \times 5$ grid, and glue the top edge to the bottom and left edge to the right, then we see the $4$ cycles exactly correspond to cells in our grid. We can assign $\pm1$ to each cycle in a checkerboard fashion. Since we glued the boundaries we have each edge is part of exactly two 4 cycles, and by our assignment one of these has $+1$ and the other $-1$. Thus the cycles are linearly dependent. 
A: See the full graph with n vertices.
Count of cycles of length 4 is more when count of edges.
