Proof of Linearity, Compatibility with the Matrix Product, and a Norm Bound for the Matrix-Vector Product

Two points of a Euclidean space are equal exactly when they agree at every coordinate, so the identities of claims 1 and 2 are proved by computing coordinates. Throughout, $(Av)_k=\sum_{i=1}^{n}A_{ki}v_i$ by Matrix-Vector Product; coordinates of sums, differences and scalar multiples of points are computed coordinatewise by Sum of Points of $\mathbb{R}^n$, Difference, Dot Product, and Orthogonality in $\mathbb{R}^n$ and Scalar Multiple of a Point of $\mathbb{R}^n$; claims 2 and 3 of Properties of Finite Sums are used as additivity and homogeneity of finite sums; and the field axioms of the field $\mathbb{R}$ are used freely in coordinatewise computations.

Claim 1. Fix a natural number $k$ with $1\le k\le m$. Distributivity gives $A_{ki}(v_i+w_i)=A_{ki}v_i+A_{ki}w_i$ for every $i$, so additivity of finite sums gives

which proves the first identity. Commutativity and associativity of multiplication give $A_{ki}(\mu v_i)=\mu\,(A_{ki}v_i)$ for every $i$, so homogeneity of finite sums gives

which proves the third identity. For the second, claims 2 and 3 of Euclidean Space $\mathbb{R}^n$ is a Real Vector Space give $(v-w)+w=v$, so the first identity, applied to the points $v-w$ and $w$, gives $A(v-w)+Aw=Av$; adding the additive inverse of $Aw$ to both sides and using claims 2 and 3 of Euclidean Space $\mathbb{R}^n$ is a Real Vector Space again gives $A(v-w)=Av-Aw$.

For the fourth identity, note first that $0\,t=0$ for every $t\in\mathbb{R}$: indeed $0\,t+0\,t=(0+0)\,t=0\,t=0\,t+0$ by distributivity and the additive-identity axiom, so $0\,t=0$ by claim 2 of Additive Cancellation and Elementary Additive Identities in a Field. Consequently every coordinate of the scalar multiple $0\,v$ is $0$, so $0\,v=0_{\mathbb{R}^n}$ by The Origin of $\mathbb{R}^n$, and likewise $0\,(Av)=0_{\mathbb{R}^m}$. The third identity with $\mu=0$ therefore gives

Claim 2. Fix a natural number $\alpha$ with $1\le\alpha\le p$. The matrix $BA$ has $p$ rows and $n$ columns, and $(BA)_{\alpha i}=\sum_{j=1}^{m}B_{\alpha j}A_{ji}$ by Product of Real Matrices, so

For each fixed $i$, homogeneity of finite sums applied to the inner sum with the factor $v_i$, together with commutativity and associativity of multiplication, gives

so that $\bigl((BA)v\bigr)_{\alpha}=\sum_{i=1}^{n}\sum_{j=1}^{m}B_{\alpha j}A_{ji}v_i$. In the same way, for each fixed $j$ homogeneity applied to the inner sum with the factor $B_{\alpha j}$ gives $B_{\alpha j}\sum_{i=1}^{n}A_{ji}v_i=\sum_{i=1}^{n}B_{\alpha j}A_{ji}v_i$, so that

The two resulting expressions are the two iterated sums of the doubly indexed family whose value at $(i,j)$ is $B_{\alpha j}A_{ji}v_i$, so they are equal by Interchange of a Finite Double Sum. Hence $\bigl((BA)v\bigr)_{\alpha}=\bigl(B(Av)\bigr)_{\alpha}$ for every $\alpha$, which proves the claim.

Claim 3. Write $c=(c_1,\dots,c_m)$, a point of $\mathbb{R}^m$, so that $C=\lVert c\rVert$.

Nonnegativity. By claim 1 of Properties of the Absolute Value in an Ordered Field we have $0\le|A_{ki}|$ for all admissible $k$ and $i$, so $0\le c_k$ for every $k$ by claim 5 of Properties of Finite Sums. By claim 1 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$,

and also $0\le\lVert v\rVert$ and $0\le\lVert Av\rVert$. Since $0\le c_k$ and $0\le\lVert v\rVert$, claim 5 of Elementary Arithmetic in an Ordered Field applied to the inequality $0\le\lVert v\rVert$ with the nonnegative factor $c_k$ gives $c_k\cdot 0\le c_k\lVert v\rVert$, and $c_k\cdot 0=0$ as shown in claim 1; hence $0\le c_k\lVert v\rVert$. The same argument gives $0\le C\lVert v\rVert$.

Step 1: a coordinate bound. Fix $k$ with $1\le k\le m$. By Matrix-Vector Product and claim 2 of Comparison and Absolute Value Bounds for Finite Sums of Real Numbers,

For each $i$, claim 4 of Properties of the Absolute Value in an Ordered Field gives $|A_{ki}v_i|=|A_{ki}|\,|v_i|$, while claim 4 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$ gives $|v_i|\le\lVert v\rVert$; multiplying the latter inequality by the nonnegative factor $|A_{ki}|$ using claim 5 of Elementary Arithmetic in an Ordered Field yields

Hence, by claim 1 of Comparison and Absolute Value Bounds for Finite Sums of Real Numbers and then homogeneity of finite sums with the factor $\lVert v\rVert$ (using commutativity of multiplication),

Combining the two displays by transitivity of the order,

Step 2: squaring the coordinate bound. By claim 1 of Properties of the Absolute Value in an Ordered Field we have $0\le|(Av)_k|$, and $0\le c_k\lVert v\rVert$ was shown above, so claim 2 of Monotonicity of Squaring on the Nonnegative Elements of an Ordered Field applied to the inequality of step 1 gives

the equality by commutativity and associativity of multiplication. Moreover $|(Av)_k|^{2}=\bigl((Av)_k\bigr)^{2}$, because by claim 1 of Properties of the Absolute Value in an Ordered Field the number $|(Av)_k|$ is either $(Av)_k$ or its additive inverse, and in either case its square is $\bigl((Av)_k\bigr)^{2}$. Therefore

Step 3: summing over the coordinates. By claim 1 of Comparison and Absolute Value Bounds for Finite Sums of Real Numbers, then homogeneity of finite sums with the factor $\lVert v\rVert^{2}$, and then the identity $C^{2}=\sum_{k=1}^{m}c_k^{2}$,

the last equality again by commutativity and associativity of multiplication. By claim 1 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$ applied to the point $Av$ of $\mathbb{R}^m$, the left-hand side equals $\lVert Av\rVert^{2}$. Thus

Step 4: conclusion. Both $\lVert Av\rVert$ and $C\lVert v\rVert$ are nonnegative, so claim 2 of Monotonicity of Squaring on the Nonnegative Elements of an Ordered Field, read from right to left, gives $\lVert Av\rVert\le C\,\lVert v\rVert$. The final assertion of the claim holds with this $C$, which does not depend on $v$.