Interpret $x_1,\dots ,x_n$ as the bits of a binary number, with $x_1$ most significant. Construct a propositional formula saying that this number is strictly less than $k$. This gives a quadratic-size formula with prescribed model count.

For $0<k<2^n$, write $k=(b_1\cdots b_n{)}_2$. For each $i$ with $b_i=1$, define the conjunctionThe empty prefix for $i=1$ is omitted. Let ${\phi }_k={\bigvee }_{i:b_i=1}{T}_i$. A Boolean valuation satisfies $T_i$ exactly when its first difference from the binary representation of $k$ is at position $i$, changing a one of $k$ to a zero. All later bits are unrestricted. Hence these cases are disjoint and cover exactly the numbers $0,\dots ,k-1$.

Alternatively, counting the disjoint cases directly givesEach $T_i$ has length $O(i)$, including its logical connectives and parentheses; the total length is at most a constant multiple of ${\sum }_{i=1}^{n}i=O(n^2)$. The endpoints are ${\phi }_0=\perp$ and ${\phi }_{2^n}=\top$. If constants are unavailable and $n\ge 1$, use $x_1\wedge \neg x_1$ and $x_1\vee \neg x_1$ instead. Assignments are counted over all $n$ specified variables, including any absent from the formula. For $n=0$, the constants describe the two possible counts, zero and one. Thus the construction covers $0\le k\le 2^n$, including the endpoint zero despite the source's word “positive”.

For example, $n=4,k=11=(1011{)}_2$ gives the disjoint cases $0\ast \ast \ast$, $100\ast$ and $1010$, with $8+2+1=11$ satisfying assignments.

Apply the propositional substitution simultaneously to the atomic variables:By distributivity and the complementary literals $Y,\neg Y$,The other disjunct simplifies using logical implication and absorption:Thus $\phi S\equiv X\vee \neg X\equiv \top$, a tautology.

Apply structural induction to the formation of a propositional formula. Let $L(\theta )$ and $R(\theta )$ count its opening and closing parentheses, and use the usual grammar generated by propositional variables, any allowed truth constants, negation, and parenthesized binary logical connectives.

An atomic variable or truth constant contains neither kind of parenthesis, so $L=R=0$. If $L(\alpha )=R(\alpha )$, prefixing negation leaves both counts unchanged. If the notation writes a negated formula with an extra pair of parentheses, it adds one to each and still preserves equality.

For a binary construction $(\alpha \circ \beta )$, where $\circ$ is an allowed binary logical connective,The two induction hypotheses make these equal. Every grammar construction preserves the property, so every propositional formula contains equally many left and right parentheses. This is balanced parentheses in propositional syntax.

Use $0$ and $1$ for false and true truth values. The truth table is:

The two satisfying rows with $A=B=1$ combine by eliminating $C$, while the remaining satisfying row has $A=B=0,C=1$. An equivalent disjunctive normal form is thereforeExpanding the logical biconditional into its two implications, and using $\neg B\to C\equiv B\vee C$, gives the conjunctive normal formEach form has exactly the same three satisfying assignments as the original propositional formula.

If $(I+A)x=0$, take its dot product with $x$ and apply (e):Hence $x=0$. A square matrix with zero null space is an invertible matrix by the rank-nullity theorem. Therefore $I+A$ is nonsingular. This proves invertibility of identity plus a real skew-symmetric matrix.

The determinant is invariant under transpose, while multiplying all $n$ rows by $-1$ multiplies it by $(-1{)}^n$. Thus, for odd integer $n$,Over the real numbers, this forces $\det A=0$, so $A$ is a singular matrix. This is the odd-dimensional skew-symmetric singularity theorem.

For a real eigenvalue $\lambda$, choose a nonzero real eigenvector $v$ with $Av=\lambda v$. By (e),Since $v^{\top }v=\Vert v{\Vert }^2>0$, $\lambda =0$. If eigenvectors were initially allowed to be complex, the real matrix $A-\lambda I$ has a nonzero real null space whenever it has a nonzero complex null space, so this choice of $v$ remains justified.

If $A$ is a skew-symmetric matrix, the scalar $x^{\top }Ax$ equals its own transpose, soand it is zero over the real numbers.

Conversely, suppose the quadratic form $x^{\top }Ax$ vanishes for every real vector. Substituting $x=e_i$ gives $a_{ii}=0$. Substituting $x=e_i+e_j$ gives $a_{ij}+a_{ji}=0$ for $i\ne j$. Therefore $A^{\top }=-A$. This proves the quadratic-form criterion for a skew-symmetric matrix:

If $A^{\top }=-A$, then the dot product satisfiesConversely, the assumed dot product identity gives $x^{\top }(A^{\top }+A)y=0$ for every $x,y$. Take $x=e_i$ and $y=e_j$ from the standard basis: every entry of $A^{\top }+A$ is zero. Hence $A^{\top }=-A$, proving the equivalence.

Split $B$ into its symmetric part and skew-symmetric part:Taking the transpose gives $S^{\top }=S$ and $K^{\top }=-K$. Thus $S$ is a symmetric matrix and $K$ a skew-symmetric matrix. These formulas also show uniqueness, since a real matrix that is both symmetric and skew-symmetric is zero.

Using linearity and involutivity of the matrix transpose,Therefore $B-B^{\top }$ is a skew-symmetric matrix.

Let $E_{ij}$ denote a matrix unit, with its only nonzero entry equal to one in row $i$, column $j$. A basis for the vector space of real skew-symmetric matrices isEach upper-triangular entry is free, its reflected lower-triangular entry is its negative, and every diagonal entry is zero. This is the basis of the space of real skew-symmetric matrices.

The dimensions of the nested images of a linear mapcan strictly decrease at most $n$ times. If all the first $n$ inclusions are strict, $\mathcal{R}(h^n)=0$ and is stable. Otherwise an earlier equality occurs and (d) makes every subsequent image equal. Thus in all casesBy the rank-nullity theorem and inclusion of the null spaces, this also gives $\ker h^n=\ker h^{2n}$. If $v\in \mathcal{R}(h^n)\cap \ker h^n$, write $v=h^{n}u$. Then $0=h^{n}v=h^{2n}u$, so $u\in \ker h^{2n}=\ker h^n$ and $v=0$. Hence the intersection is zero. Finally the rank-nullity theorem givesZero intersection and this dimension sum proveThis is the finite-dimensional Fitting decomposition. It includes the zero-dimensional case, for which $V=0$ and the assertion is immediate.

Apply $h$ to both sides of $\mathcal{R}(h^m)=\mathcal{R}(h^{m+1})$. Because $h(\mathcal{R}(h^j))=\mathcal{R}(h^{j+1})$, we obtain $\mathcal{R}(h^{m+1})=\mathcal{R}(h^{m+2})$. Repeating this argument proves equality at every later step. More formally, an induction on $k$ givesThe base case is $k=0$; the induction step follows from applying the linear map $h$ and then the assumed first equality. Thus one equality permanently stabilizes the descending sequence of images of a linear map.

For $v\in \mathcal{R}(h^{m+k})$, choose $u$ with $v=h^{m+k}u=h^m(h^{k}u)$. Thus $v\in \mathcal{R}(h^m)$, provingThis is the decreasing-image part of stabilization of images of powers of a linear map. The convention $h^0={\mathrm{id}}_V$ includes $m=0$ and $k=0$.

Take $V={\mathbb{R}}^2$ and the linear map $h(x,y)=(y,0)$. ThenTheir intersection is nonzero and their sum is only one-dimensional. Hence $V\ne \mathcal{R}(h)\oplus \mathcal{N}(h)$. This nilpotent linear map has $h^2=0$, illustrating why taking sufficiently high powers changes the situation.

Take $V={\mathbb{R}}^2$ and the linear map $h(x,y)=(x,0)$. ThenThese two vector subspaces have zero intersection and together span ${\mathbb{R}}^2$, so $V=\mathcal{R}(h)\oplus \mathcal{N}(h)$ as a direct sum of vector spaces.

Fix one common eigenvector $v\ne 0$, and write $A{A}^{\top }v=\lambda v$ and $B{B}^{\top }v=\mu v$. By (d),so $\lambda \mu v=0$ and at least one of the two eigenvalues is zero.

To exclude both being zero, use the kernel of a Gram product identity:If both products annihilate $v$, then $A^{\top }v=B^{\top }v=0$. By (b), $v\in \mathrm{im}L$, and by (e), this is $\mathrm{im}B$. On the other hand, $B^{\top }v=0$ makes $v$ orthogonal to every vector in $\mathrm{im}B$. In particular $v$ is orthogonal to itself, so $\Vert v{\Vert }^2=0$ and $v=0$, a contradiction.

Therefore each specified common eigenvector belongs to exactly one of $\ker (A{A}^{\top })$ and $\ker (B{B}^{\top })$. Both eigenvalues are nonnegative by the displayed squared-norm identities, so the other eigenvalue is strictly positive. This is the spectral mechanism behind orthogonal null-space completion of a square matrix.

Expand the product and use (d) together with its transpose:Indeed $A{B}^{\top }=0$ and $B{A}^{\top }=(A{B}^{\top }{)}^{\top }=0$.

Both $L$ and $R$ have $m$ linearly independent columns. The Gram matrix $R^{\top }R$ is invertible becauseConsequently $R^{\top }$ is a surjective linear map: for any $y\in {\mathbb{R}}^m$, the choice $x=R(R^{\top }R{)}^{-1}y$ satisfies $R^{\top }x=y$. HenceThe latter image of a linear map has dimension $m$, giving $\mathrm{rank}B=m$. If $m=0$, $B=0$ and the conclusion is immediate. This argument explains why the product retains its full possible matrix rank; a general product of two matrices need not do so.