One of the most basic facts of linear algebra is that whenever you have \(n+1\) vectors in an \(n\)-dimensional vectors space, there must be one of your vectors which can be expressed as a linear combination of the other vectors. This seemingly simple fact can prove some really interesting combinatorial statements.
Not sure if this one counts:Theorem. Let \(x_1,x_2,\ldots, x_k\) be \(k\) linearly-independent vectors in, say, \(\mathbb{F}_2^{n}\). Then there is a vector \(y\) in the span of \(x_1,x_2,\ldots, x_k\) with at least \(k\) non-zero entries.
Proof. Write the \(x_1,x_2,\ldots, x_k\) as an \(n \times k\) matrix. It must have a \(k\times k\) invertible submatrix. Why? Because just delete rows one at a time.
Theorem. The vertices of any graph \(G\) can be partitioned into two parts \(V_1,V_2\) such that \(G[V_1], G[V_2]\) have all vertices having even degree.
Proof.
Let \(x_i\in \mathbb{F}_2\) be a binary variable indicating which part to put vertex \(i\) in. Then write some equations: For \(i\) with odd degree write: \[x_i + \sum_{j\in N(i)}x_j = 1\] For \(i\) with even degree write: \[\sum_{j\in N(i)}x_j = 0.\]
claim: It must have a solution. proof: you might be highly skeptical: “thaht matrix needn’t be invertible.” well fine, but we don’t need it to be invertible, we just need this very specific vector to be in its image.
Letting \(D\) be a diagonal matrix with \(D_{i,i}\) being the degree of vertex \(i\), and letting \(d\) be a vector with \(d_i\) being the degree of vertex \(i\), we have:
\[ d \in Im (A+D)\] This is equiv to \[ (Im (A+D)) ^{\perp} \subseteq d^{\perp} .\]
Take \(x\in( Im(A+D))^{\perp}\). Then for all \(i\), \[\sum_j x_j (a_{i,j}+d_{i,j}) = 0,\] so \[\sum_j x_j a_{i,j} = x_i d_i.\] Then \[\sum_i x_i \sum_j x_j a_{i,j} = \sum_i x_i^{2}d_i \]
But then of course \[\sum_i x_i d_i = \sum_{i<j} (a_{i,j}+a_{j,i})x_{i}x_j + \sum_{i}x_i a_{i,i} = 0.\] That is, \(x\perp d\) as desired.
Intuitively what just happened? “weighted sums are kind of powerful” is the extent to which I understand this so far.