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

$$\bigl(A(v+w)\bigr)_k=\sum_{i=1}^{n}\bigl(A_{ki}v_i+A_{ki}w_i\bigr)=(Av)_k+(Aw)_k=(Av+Aw)_k ,$$

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

$$\bigl(A(\mu v)\bigr)_k=\sum_{i=1}^{n}\mu\,(A_{ki}v_i)=\mu\,(Av)_k=\bigl(\mu\,(Av)\bigr)_k ,$$

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

$$A\,0_{\mathbb{R}^n}=A(0\,v)=0\,(Av)=0_{\mathbb{R}^m}.$$

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

$$\bigl((BA)v\bigr)_{\alpha}=\sum_{i=1}^{n}(BA)_{\alpha i}\,v_i=\sum_{i=1}^{n}\Bigl(\sum_{j=1}^{m}B_{\alpha j}A_{ji}\Bigr)v_i .$$

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

$$\Bigl(\sum_{j=1}^{m}B_{\alpha j}A_{ji}\Bigr)v_i=\sum_{j=1}^{m}B_{\alpha j}A_{ji}v_i ,$$

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

$$\bigl(B(Av)\bigr)_{\alpha}=\sum_{j=1}^{m}B_{\alpha j}(Av)_j=\sum_{j=1}^{m}\sum_{i=1}^{n}B_{\alpha j}A_{ji}v_i .$$

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$,

$$0\le C,\qquad C^{2}=\sum_{k=1}^{m}c_k^{2},$$

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,

$$|(Av)_k|=\Bigl|\sum_{i=1}^{n}A_{ki}v_i\Bigr|\le\sum_{i=1}^{n}|A_{ki}v_i| .$$

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

$$|A_{ki}v_i|=|A_{ki}|\,|v_i|\le|A_{ki}|\,\lVert v\rVert .$$

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),

$$\sum_{i=1}^{n}|A_{ki}v_i|\le\sum_{i=1}^{n}|A_{ki}|\,\lVert v\rVert=\Bigl(\sum_{i=1}^{n}|A_{ki}|\Bigr)\lVert v\rVert=c_k\,\lVert v\rVert .$$

Combining the two displays by transitivity of the order,

$$|(Av)_k|\le c_k\,\lVert v\rVert .$$

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

$$|(Av)_k|^{2}\le\bigl(c_k\lVert v\rVert\bigr)^{2}=c_k^{2}\,\lVert v\rVert^{2},$$

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

$$\bigl((Av)_k\bigr)^{2}\le c_k^{2}\,\lVert v\rVert^{2}\qquad\text{for every }k\text{ with }1\le k\le m .$$

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}$,

$$\sum_{k=1}^{m}\bigl((Av)_k\bigr)^{2}\le\sum_{k=1}^{m}c_k^{2}\,\lVert v\rVert^{2}=\Bigl(\sum_{k=1}^{m}c_k^{2}\Bigr)\lVert v\rVert^{2}=C^{2}\,\lVert v\rVert^{2}=\bigl(C\,\lVert v\rVert\bigr)^{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

$$\lVert Av\rVert^{2}\le\bigl(C\,\lVert v\rVert\bigr)^{2}.$$

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$.