Quadratic Forms on Complete Graphs

From the Spectrum to a Quadratic Form

The adjacency matrix records which pairs of vertices are joined, while a quadratic form evaluates how a vector interacts with all those adjacencies at once. For a complete graph, the spectrum gives a particularly simple way to make this calculation: separate the vector into its constant component and its component whose coordinates sum to zero. The two parts contribute with opposite signs.

Throughout, let \(n\ge 1\), let \(K_n\) be the simple complete graph on vertex set \(\{1,\dots,n\}\), and take vectors \(x\in\mathbb{R}^n\). Write \(x^T\) for the transpose of \(x\), and \(\|x\|^2=\sum_{i=1}^n x_i^2\) for its squared Euclidean norm. The adjacency quadratic form of \(K_n\) is the scalar \(x^T\mathbf{A}(K_n)x\).

For \(K_n\), every two distinct vertices are adjacent, and no vertex is adjacent to itself. Thus \(\mathbf{A}(K_n)\) has zero diagonal and all off-diagonal entries equal to \(1\). The earlier result on the spectrum of complete graphs gives eigenvalue \(n-1\) on the constant vectors and eigenvalue \(-1\) on the vectors whose coordinates sum to zero, when \(n\ge2\). We now use this decomposition to obtain an exact formula for every vector.

The Eigenspace Decomposition and Exact Formula

Let \(\mathbf{1}=(1,\dots,1)^T\). For \(x=(x_1,\dots,x_n)^T\), its mean coordinate is \(\mu=(x_1+\cdots+x_n)/n\). Define \(x_{\parallel}=\mu\mathbf{1}\) and \(x_{\perp}=x-\mu\mathbf{1}\). Then \(x=x_{\parallel}+x_{\perp}\), and the coordinates of \(x_{\perp}\) sum to zero. Moreover, \(x_{\parallel}\) is orthogonal to \(x_{\perp}\), since \(\mathbf{1}^Tx_{\perp}=0\).

Proof. The adjacency matrix of \(K_n\) has \(1\) in every off-diagonal position and \(0\) on the diagonal. If \(y\) has coordinate sum zero, then the \(i\)-th coordinate of \(\mathbf{A}(K_n)y\) is \(\sum_{j\ne i}y_j=-y_i\). If \(y=c\mathbf{1}\), then each coordinate of \(\mathbf{A}(K_n)y\) is \((n-1)c\). These computations give the stated eigenvalues and show that \(\mathbf{A}(K_n)x=(n-1)x_{\parallel}-x_{\perp}\) when \(n\ge2\). Taking the inner product with \(x=x_{\parallel}+x_{\perp}\), the cross terms vanish because the two components are orthogonal. Therefore \(x^T\mathbf{A}(K_n)x=(n-1)\|x_{\parallel}\|^2-\|x_{\perp}\|^2\). Also, \(\|x_{\parallel}\|^2=n\mu^2=(\sum_i x_i)^2/n\), and orthogonality gives \(\|x\|^2=\|x_{\parallel}\|^2+\|x_{\perp}\|^2\). Substituting these identities yields \((n-1)\|x_{\parallel}\|^2-\|x_{\perp}\|^2=n\|x_{\parallel}\|^2-\|x\|^2=(\sum_i x_i)^2-\sum_i x_i^2\). When \(n=1\), the adjacency matrix is the \(1\)-by-\(1\) zero matrix; \(x_{\perp}=0\), and both expressions in the theorem equal zero. \(\square\)

The coordinate formula also follows by expanding the square of the sum: \((\sum_i x_i)^2=\sum_i x_i^2+2\sum_{i<j}x_ix_j\). Since every pair \(i<j\) is an edge of \(K_n\), this gives the same edge-sum expression. The eigenspace formula and the coordinate formula are useful for different reasons: one highlights the signs of the two eigenspaces, while the other is a quick calculation directly from the coordinates.

What the Signs Tell Us

The decomposition describes the sign of the form without requiring an entry-by-entry matrix multiplication. A nonzero constant vector has a positive value when \(n\ge2\), because its zero-sum component vanishes and its constant component has positive squared norm. A nonzero zero-sum vector has a negative value, because its constant component vanishes and its zero-sum component has positive squared norm. A general vector can have either sign, and a nonzero vector can even give zero when the two contributions balance.

Proof. Choose the nonzero constant vector \(x=\mathbf{1}\). Then \(x_{\perp}=0\), \(\|x_{\parallel}\|^2=n>0\), and the theorem gives \(x^T\mathbf{A}(K_n)x=(n-1)n>0\). Choose the nonzero zero-sum vector \(y=(1,-1,0,\dots,0)^T\), which exists because \(n\ge2\). It has \(y_{\parallel}=0\) and \(\|y_{\perp}\|^2=1^2+(-1)^2=2\), so its quadratic form is \(-2<0\). Finally, for any \(x\), the theorem expresses the value as the difference \((n-1)\|x_{\parallel}\|^2-\|x_{\perp}\|^2\). That difference is zero if and only if its two terms are equal, which is precisely the stated condition. \(\square\)

Common Pitfall: Counting Each Edge Only Once

The edge-sum formula has a factor of \(2\). A common mistake is to sum \(x_ux_v\) over the edges and report that sum as \(x^T\mathbf{A}x\). For the \(K_4\) example, the edge products sum to \(-1\), but the quadratic form is \(-2\), not \(-1\). The reason is that the matrix product includes both the \((u,v)\) and \((v,u)\) entries for every edge.

A second useful check is to compare the answer with the coordinate identity \((\sum_i x_i)^2-\sum_i x_i^2\). For \(x=(1,2,0,-1)^T\), this gives \(2^2-(1+4+0+1)=4-6=-2\), which catches the missing-factor error. This identity applies to the adjacency matrix of a complete graph: it should not be transferred unchanged to a different graph, where not every pair is an edge.

The decomposition also guards against another misreading: the form is not negative on every vector simply because the zero-sum eigenspace has eigenvalue \(-1\). The constant eigenspace contributes positively for \(n\ge2\). To evaluate a vector reliably, identify both components, or use the coordinate formula and then check with the edge sum.