Proof of Rules for Symmetric and Positive Semidefinite Matrices: Closure, Self-Adjointness, Polarization, Congruence and Cones

Each result cited is universally quantified over the data in its own statement.

We work in Routine Facts Used Without Citation: Arithmetic, Maps, Predicativity and Indices. Membership in $\mathcal{S}(n)$ is as in Symmetric Real Matrices and the Set $\mathcal{S}(n)$ §membership; entries of sums, differences and scalar multiples of matrices are as in Real Matrices: the Set of Real m x n Matrices with Their Entrywise Operations §operations, and two matrices of the same size are equal when all their entries agree, by Real Matrices: the Set of Real m x n Matrices with Their Entrywise Operations §equality. Every element of $\mathcal{S}(n)$ is symmetric by Symmetric Real Matrices and the Set $\mathcal{S}(n)$ §set, so $A^{\top}=A$ and $B^{\top}=B$ by Symmetric Real Matrices and the Set $\mathcal{S}(n)$ §symmetric. Positive semidefiniteness and positive definiteness are as in Positive Semidefinite and Positive Definite Real Matrices §psd and Positive Semidefinite and Positive Definite Real Matrices §pd.

Clause closure. Let $i,j\in[n]$. Then $A_{ij}=A_{ji}$ and $B_{ij}=B_{ji}$, so

$$(A+B)_{ij}=A_{ij}+B_{ij}=A_{ji}+B_{ji}=(A+B)_{ji},\quad (A-B)_{ij}=A_{ij}-B_{ij}=A_{ji}-B_{ji}=(A-B)_{ji},\quad (tA)_{ij}=t\,A_{ij}=t\,A_{ji}=(tA)_{ji}.$$

The zero matrix is the constant map with value $0$, by Real Matrices: the Set of Real m x n Matrices with Their Entrywise Operations §zero, so $0_{ij}=0=0_{ji}$. The entries $\delta_{ij}$ of $I_{n}$ are $1$ if $i=j$ and $0$ if $i\neq j$, by Identity Matrix and Standard Basis Vectors §identity, so $\delta_{ij}=\delta_{ji}$. Hence $0$, $I_{n}$, $A+B$, $A-B$ and $tA$, all in $\mathcal{M}_{n}(\mathbb{R})$, lie in $\mathcal{S}(n)$.

Clause self-adjoint. By Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §adjoint with $m=n$ and $w=y$, and $A^{\top}=A$,

$$(Ax)\cdot y=x\cdot(A^{\top}y)=x\cdot(Ay).$$

Clause entries. Let $P\in\mathcal{M}_{n}(\mathbb{R})$ and $i,j\in[n]$; symmetry of $P$ is not used. By Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §column, $(Pe_{j})_{k}=P_{kj}$ for $k\in[n]$, and $(e_{i})_{k}=\delta_{ki}$ by Identity Matrix and Standard Basis Vectors §basis. By The Dot Product on $\mathbb{R}^n$ §dot-product,

$$e_{i}\cdot(Pe_{j})=\sum_{k=1}^{n}\delta_{ki}P_{kj}.$$

For $k\neq i$ the term is $0\cdot P_{kj}=0$, by Identity Matrix and Standard Basis Vectors §identity. Since $\mathbb{R}$ is an ordered field by The Real Numbers, with the Natural Numbers, Integers and Rationals Identified with Subsets of the Reals, and Completeness §reals, hence a commutative ring by Ordered Fields §ordered-field and Fields §field, Sums over Finite Sets in a Commutative Ring and in an Ordered Field: Distributivity, Products of Sums, Vanishing Terms, Sums over Pairs, Expanding Products of Sums, Counting, Comparison, Monotonicity and the Triangle Inequality §vanishing with $y=i$ gives $e_{i}\cdot(Pe_{j})=\delta_{ii}P_{ij}=P_{ij}$.

Clause polarization. Let $D\in\{A,B\}$ and $u,v\in\mathbb{R}^{n}$. By Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §matrix-vector, $D(u+v)=Du+Dv$; by The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §second and then The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §first,

$$(u+v)\cdot(D(u+v))=(u+v)\cdot(Du)+(u+v)\cdot(Dv)=u\cdot(Du)+v\cdot(Du)+u\cdot(Dv)+v\cdot(Dv).$$

By The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §symmetric and the clause self-adjoint (applied to $D$, with $x=u$ and $y=v$), $v\cdot(Du)=(Du)\cdot v=u\cdot(Dv)$. Hence

$$2\,u\cdot(Dv)=(u+v)\cdot(D(u+v))-u\cdot(Du)-v\cdot(Dv).\tag{$*$}$$

Now assume $z\cdot(Az)=z\cdot(Bz)$ for every $z\in\mathbb{R}^{n}$, and let $i,j\in[n]$. Applying $(*)$ with $u=e_{i}$ and $v=e_{j}$ to $D=A$ and to $D=B$, the right-hand sides agree term by term (with $z=e_{i}+e_{j}$, $z=e_{i}$ and $z=e_{j}$), so $2\,e_{i}\cdot(Ae_{j})=2\,e_{i}\cdot(Be_{j})$ and $e_{i}\cdot(Ae_{j})=e_{i}\cdot(Be_{j})$. By the clause entries, applied with $P=A$ and with $P=B$, $A_{ij}=B_{ij}$. Hence $A=B$.

Quadratic forms of sums and multiples. Let $z\in\mathbb{R}^{n}$. By Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §matrix-vector, $(A+B)z=Az+Bz$ and $(tA)z=t(Az)$, so by The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §second

$$z\cdot((A+B)z)=z\cdot(Az)+z\cdot(Bz),\qquad z\cdot((tA)z)=t\,\bigl(z\cdot(Az)\bigr).\tag{$**$}$$

By the clause closure, $A+B$ and $tA$ lie in $\mathcal{S}(n)$.

Clause cone-psd. If $A$ and $B$ are positive semidefinite and $t\ge0$, then for every $z\in\mathbb{R}^{n}$, $z\cdot(Az)\ge0$ and $z\cdot(Bz)\ge0$, so both right-hand sides of $(**)$ are $\ge0$; as $z$ is arbitrary, $A+B$ and $tA$ are positive semidefinite.

Clause cone-pd. If $A$ is positive definite, $B$ is positive semidefinite, $t>0$ and $z\in\mathbb{R}^{n}$ with $z\neq0$, then $z\cdot(Az)>0$ and $z\cdot(Bz)\ge0$, so both right-hand sides of $(**)$ are $>0$; hence $A+B$ and $tA$ are positive definite.

Clause identity-pd. $I_{n}\in\mathcal{S}(n)$ by the clause closure, and $I_{n}z=z$ by Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §matrix-vector. For $z\neq0$, $z\cdot z\ge0$ by The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §nonnegative and $z\cdot z\neq0$ by The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §definite, so $z\cdot(I_{n}z)=z\cdot z>0$; thus $I_{n}$ is positive definite.

Clause pd-psd. Let $D\in\mathcal{S}(n)$ be positive definite and $z\in\mathbb{R}^{n}$. If $z\neq0$, then $z\cdot(Dz)>0$. If $z=0$, then $Dz=0$ by Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §matrix-vector and $0\cdot0=0$ by The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §definite, so $z\cdot(Dz)=0$. In both cases $z\cdot(Dz)\ge0$, so $D$ is positive semidefinite.

Clause congruence. Let $M=(C^{\top}A)C$, where $C^{\top}\in\mathcal{M}_{m\times n}(\mathbb{R})$, $C^{\top}A\in\mathcal{M}_{m\times n}(\mathbb{R})$ and $M\in\mathcal{M}_{m}(\mathbb{R})$. By Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §transpose, used for $(PQ)^{\top}=Q^{\top}P^{\top}$ twice and for $(C^{\top})^{\top}=C$, together with $A^{\top}=A$, and then by Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §associative,

$$M^{\top}=C^{\top}(C^{\top}A)^{\top}=C^{\top}\bigl(A^{\top}(C^{\top})^{\top}\bigr)=C^{\top}(AC)=(C^{\top}A)C=M.$$

So $M$ is symmetric by Symmetric Real Matrices and the Set $\mathcal{S}(n)$ §symmetric, and $M\in\mathcal{S}(m)$ by Symmetric Real Matrices and the Set $\mathcal{S}(n)$ §set.

Assume $A$ is positive semidefinite, and let $z\in\mathbb{R}^{m}$ and $u=Cz\in\mathbb{R}^{n}$. Applying the rule $(PQ)z=P(Qz)$ of Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §matrix-vector twice, $Mz=(C^{\top}A)u=C^{\top}(Au)$. By Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §adjoint, with $C$ in place of $A$, $z$ in place of $x$ and $w=Au$,

$$z\cdot(Mz)=z\cdot\bigl(C^{\top}(Au)\bigr)=(Cz)\cdot(Au)=u\cdot(Au)\ge0.$$

As $M\in\mathcal{S}(m)$ and $z$ is arbitrary, $M$ is positive semidefinite.

Clause gram. $C^{\top}I_{n}=C^{\top}$ by Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §identity, so $C^{\top}C=(C^{\top}I_{n})C$. Since $I_{n}\in\mathcal{S}(n)$ by the clause closure, and $I_{n}$ is positive semidefinite by the clauses identity-pd and pd-psd, the clause congruence with $I_{n}$ in place of $A$ shows that $C^{\top}C\in\mathcal{S}(m)$ and that $C^{\top}C$ is positive semidefinite.