Proof of Rules for the Operator Norm: Bound, Least Constant, Definiteness, Homogeneity, Triangle Inequality and Products

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. $\mathbb{R}$ is an ordered field by The Real Numbers Form an Ordered Field in Which Every Nonempty Set Bounded Above Has a Supremum §ordered-field, so the results on ordered fields cited below apply to it. For every point $y$ of a Euclidean space, $\lVert y\rVert\ge0$ by Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square §square.

Two facts on suprema. Let $k,l\in\mathbb{N}$ and $D\in\mathcal{M}_{k\times l}(\mathbb{R})$. By The Operator Norm of a Real Matrix §norm, $\lVert D\rVert=\sup N_{D}$, where $N_{D}=\{\lVert Dx\rVert:x\in U_{l}\}$ is the set of The Set of Lengths ‖Ax‖ over the Unit Ball Has a Supremum, and the Supremum Map Exists with $k$, $l$ and $D$ for its $m$, $n$ and $A$; by The Set of Lengths ‖Ax‖ over the Unit Ball Has a Supremum, and the Supremum Map Exists §membership, for every set $s$, $s\in N_{D}$ if and only if $s=\lVert Dx\rVert$ for some $x\in\mathbb{R}^{l}$ with $\lVert x\rVert\le1$. By Bounds, Least and Greatest Elements, Suprema and Infima for a Partial Order §supremum, $\lVert D\rVert$ is the least element of the set of upper bounds of $N_{D}$ in $\mathbb{R}$; so, by Bounds, Least and Greatest Elements, Suprema and Infima for a Partial Order §least and Bounds, Least and Greatest Elements, Suprema and Infima for a Partial Order §bounds:

(S1) $\lVert Dx\rVert\le\lVert D\rVert$ for every $x\in\mathbb{R}^{l}$ with $\lVert x\rVert\le1$;

(S2) if $b\in\mathbb{R}$ and $\lVert Dx\rVert\le b$ for every $x\in\mathbb{R}^{l}$ with $\lVert x\rVert\le1$, then $\lVert D\rVert\le b$.

The clauses nonnegative, bound and least are proved for $D$ in place of $A$, for all $k,l\in\mathbb{N}$ and $D\in\mathcal{M}_{k\times l}(\mathbb{R})$, and are used below in that generality.

A unit vector. Let $l\in\mathbb{N}$ and let $e_{1}\in\mathbb{R}^{l}$ be the first standard basis vector (it exists by The Matrix Product, Matrix-Vector Product, Transpose, Trace, Identity Matrix and Standard Basis Vectors Exist and Are Unique §basis, as $1\in[l]$ by The Segments [n]: Each Is a Set, and 1 Lies in [n] for n ∈ ℕ §one). By Standard Basis Vectors of ℝ^q: Coordinates, Orthonormality and Unit Length §unit, $\lVert e_{1}\rVert=1$.

Clause nonnegative. The origin $0$ of $\mathbb{R}^{l}$ has $\lVert0\rVert=0\le1$ by Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square §vanishing, and $D0=0$ by Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §matrix-vector, so $\lVert D0\rVert=0$ by Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square §vanishing. By (S1), $0\le\lVert D\rVert$.

Clause bound. Let $x\in\mathbb{R}^{l}$. If $x=0$, then $Dx=0$ by Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §matrix-vector, and $\lVert Dx\rVert=0=\lVert D\rVert\cdot0=\lVert D\rVert\,\lVert x\rVert$ by Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square §vanishing. Let $x\neq0$ and $r=\lVert x\rVert$. Then $0\le r$, and $r\neq0$ by Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square §vanishing, so $0<r$. Let $r^{-1}$ be the reciprocal of $r$, so $r\cdot r^{-1}=1$; by Rules of Arithmetic and Order in an Ordered Field §positive-reciprocal, $0<r^{-1}$, so $|r^{-1}|=r^{-1}$ by Absolute Value in an Ordered Field §absolute-value. Let $u=r^{-1}x$. By Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square §homogeneity, $\lVert u\rVert=r^{-1}r=1$, so (S1) gives $\lVert Du\rVert\le\lVert D\rVert$. By Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §matrix-vector, $Du=r^{-1}(Dx)$, so $\lVert Du\rVert=r^{-1}\lVert Dx\rVert$ by Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square §homogeneity. Thus $r^{-1}\lVert Dx\rVert\le\lVert D\rVert$, and Rules of Arithmetic and Order in an Ordered Field §order-product with $r>0$ for its $z$ gives

$$\lVert Dx\rVert=(r^{-1}\lVert Dx\rVert)\,r\le\lVert D\rVert\,r=\lVert D\rVert\,\lVert x\rVert.$$

Clause least. Let $c\in\mathbb{R}$ with $\lVert Dx\rVert\le c\,\lVert x\rVert$ for every $x\in\mathbb{R}^{l}$. With the unit vector $e_{1}\in\mathbb{R}^{l}$ above, $0\le\lVert De_{1}\rVert\le c\,\lVert e_{1}\rVert=c$, so $0\le c$. Now let $x\in\mathbb{R}^{l}$ with $\lVert x\rVert\le1$. By Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares §nonnegative-scaling, with $c$ for its $z$, $c\,\lVert x\rVert\le c$, so $\lVert Dx\rVert\le c$. By (S2), $\lVert D\rVert\le c$.

Clause definite. Suppose $A=0$. For $x\in\mathbb{R}^{n}$ and $i\in[m]$, the entries of $A$ are $0$ by Real Matrices: the Set of Real m x n Matrices with Their Entrywise Operations §zero, so by Matrix-Vector Product §product and Finite Sums in a Commutative Ring and in an Ordered Field: Distributivity, Differences, Telescoping, Constant Terms, Comparison and the Triangle Inequality §constant

$$(Ax)_{i}=\sum_{j=1}^{n}0\cdot x_{j}=\sum_{j=1}^{n}0=n\cdot0=0;$$

so $Ax$ is the origin by Euclidean Space $\mathbb{R}^n$: n-Tuples of Real Numbers with Their Componentwise Operations §equality and Euclidean Space $\mathbb{R}^n$: n-Tuples of Real Numbers with Their Componentwise Operations §origin, and $\lVert Ax\rVert=0=0\cdot\lVert x\rVert$ by Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square §vanishing. The clause least with $c=0$ gives $\lVert A\rVert\le0$, and the clause nonnegative gives $0\le\lVert A\rVert$; so $\lVert A\rVert=0$. Conversely, suppose $\lVert A\rVert=0$, and let $i\in[m]$ and $j\in[n]$, with $e_{j}\in\mathbb{R}^{n}$ the $j$-th standard basis vector (it exists by The Matrix Product, Matrix-Vector Product, Transpose, Trace, Identity Matrix and Standard Basis Vectors Exist and Are Unique §basis). By the clause bound, $0\le\lVert Ae_{j}\rVert\le0\cdot\lVert e_{j}\rVert=0$, so $\lVert Ae_{j}\rVert=0$ and $Ae_{j}$ is the origin of $\mathbb{R}^{m}$ by Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square §vanishing. By Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §column, $A_{ij}=(Ae_{j})_{i}=0$, the components of the origin being $0$ by Euclidean Space $\mathbb{R}^n$: n-Tuples of Real Numbers with Their Componentwise Operations §origin. By Real Matrices: the Set of Real m x n Matrices with Their Entrywise Operations §equality and Real Matrices: the Set of Real m x n Matrices with Their Entrywise Operations §zero, $A=0$.

Clause homogeneity. First let $A'\in\mathcal{M}_{m\times n}(\mathbb{R})$ and $t'\in\mathbb{R}$ be arbitrary. For $x\in\mathbb{R}^{n}$, $(t'A')x=t'(A'x)$ by Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §matrix-vector, so by Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square §homogeneity, the clause bound and Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares §nonnegative-scaling with $|t'|\ge0$ (Rules of Arithmetic and Order in an Ordered Field §absolute-value) for its $z$,

$$\lVert(t'A')x\rVert=|t'|\,\lVert A'x\rVert\le|t'|\,\lVert A'\rVert\,\lVert x\rVert.$$

By the clause least, $\lVert t'A'\rVert\le|t'|\,\lVert A'\rVert$. $(\ast)$

With $A'=A$ and $t'=t$, $(\ast)$ gives $\lVert tA\rVert\le|t|\,\lVert A\rVert$. For the reverse inequality: if $t=0$, then $|t|=0$ by Rules of Arithmetic and Order in an Ordered Field §absolute-value, and $|t|\,\lVert A\rVert=0\le\lVert tA\rVert$ by the clause nonnegative. If $t\neq0$, let $s=t^{-1}$, so $s\,t=1$ by Negatives, Differences, Reciprocals and Quotients §reciprocal. By Real Matrices: the Set of Real m x n Matrices with Their Entrywise Operations §operations, $(s(tA))_{ij}=s\,(t\,A_{ij})=A_{ij}$ for all $i\in[m]$ and $j\in[n]$, so $s(tA)=A$ by Real Matrices: the Set of Real m x n Matrices with Their Entrywise Operations §equality, and $(\ast)$ with $A'=tA$ and $t'=s$ gives $\lVert A\rVert\le|s|\,\lVert tA\rVert$. As $|t|\ge0$ and $|t|\neq0$ by Rules of Arithmetic and Order in an Ordered Field §absolute-value, $0<|t|$, and Rules of Arithmetic and Order in an Ordered Field §order-product with $|t|$ for its $z$, together with $|t|\,|s|=|ts|=|1|=1$ (Rules of Arithmetic and Order in an Ordered Field §absolute-value and Absolute Value in an Ordered Field §absolute-value), gives

$$|t|\,\lVert A\rVert\le|t|\,|s|\,\lVert tA\rVert=\lVert tA\rVert.$$

In both cases $|t|\,\lVert A\rVert\le\lVert tA\rVert$, so $\lVert tA\rVert=|t|\,\lVert A\rVert$.

Clause triangle. Let $x\in\mathbb{R}^{n}$. By Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §matrix-vector, $(A+B)x=Ax+Bx$. By Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square §triangle, the clause bound for $A$ and for $B$, and Rules of Arithmetic and Order in an Ordered Field §order-sum,

$$\lVert(A+B)x\rVert\le\lVert Ax\rVert+\lVert Bx\rVert\le\lVert A\rVert\,\lVert x\rVert+\lVert B\rVert\,\lVert x\rVert=(\lVert A\rVert+\lVert B\rVert)\,\lVert x\rVert.$$

By the clause least, $\lVert A+B\rVert\le\lVert A\rVert+\lVert B\rVert$.

Clause product. The product $AC\in\mathcal{M}_{m\times p}(\mathbb{R})$ is the value of the map of The Matrix Product, Matrix-Vector Product, Transpose, Trace, Identity Matrix and Standard Basis Vectors Exist and Are Unique §product, by Product of Real Matrices §product. Let $z\in\mathbb{R}^{p}$. By Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §matrix-vector, $(AC)z=A(Cz)$. By the clause bound for $A$ at $Cz\in\mathbb{R}^{n}$, then the clause bound for $C$ and Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares §nonnegative-scaling with $\lVert A\rVert\ge0$ (clause nonnegative) for its $z$,

$$\lVert(AC)z\rVert=\lVert A(Cz)\rVert\le\lVert A\rVert\,\lVert Cz\rVert\le\lVert A\rVert\,\lVert C\rVert\,\lVert z\rVert.$$

By the clause least, applied to $AC\in\mathcal{M}_{m\times p}(\mathbb{R})$ with $\lVert A\rVert\,\lVert C\rVert$ for $c$, $\lVert AC\rVert\le\lVert A\rVert\,\lVert C\rVert$.