# Shae's Ramblings

Stuff I find slightly meaningful and close to achievable

## Matrix-vector product inequalities

This post aims at gathering different inequalities pertaining to the product $\mathrm{A}x$ where $\mathrm{A}$ is a $m\times n$ matrix, and $v\in\mathbb{R}^n$ is a vector. We will decompose the matrix $\mathrm{A}$ in terms of its column vectors $a_j$ and its row vectors $\tilde{a}_i^\mathsf{T}$:

$$\mathrm{A} = \begin{bmatrix} a_1 & \dots & a_n \end{bmatrix} = \begin{bmatrix} \tilde{a}_1^\mathsf{T} \\ \vdots \\ \tilde{a}_m^\mathsf{T} \end{bmatrix}$$

## Euclidean norm

The quantity
$$\lVert\mathrm{A}x \rVert_2^2 = \sum_{i=1}^m \left(\tilde{a}_i^\mathsf{T}x\right)^2$$
can be decomposed using the cauchy-schwartz inequality to obtain

$$\lVert\mathrm{A}x \rVert_2^2 \leq \left(\sum_{i=1}^m \lVert\tilde{a}_i\rVert_2^2\right)\, \lVert x\rVert_2^2 = \lVert \mathrm{A} \rVert_{\mathrm{F}}^2 \, \lVert x\rVert_2^2$$

thus there is a $M = \lVert \mathrm{A} \rVert_{\mathrm{F}}$ such that $\lVert\mathrm{A}x \rVert_2 \leq M\lVert x\rVert_2^2$.

This means all matrices are continuous & bounded linear maps for the $l_2$ norm.

## Manhattan norm

Suppose we wish to measure with input and output spaces using the $l_1$ norm. The quantity
$$\lVert\mathrm{A}x \rVert_1 = \sum_{i=1}^m \lvert\tilde{a}_i^\mathsf{T}x\rvert = \sum_{i=1}^m \lvert\sum_{j=1}^n a_{ij}x_j\rvert$$
can be upper-bounded using the finite-sum generalization of the scalar inequality $\lvert a + b \rvert \leq \lvert a\rvert + \lvert b \rvert$.
Denoting $\lVert \mathrm{A} \rVert_1$ the sum of the unsigned entries $\lvert a_{ij} \rvert$ we have the inequality:

$$\lVert\mathrm{A}x \rVert_1 \leq \lVert\mathrm{A} \rVert_1 \lVert x \rVert_1$$

we can conclude similarly to the first section.

## Infinity norm

Assume we now use the infinity norm $\lVert \cdot \rVert_\infty$, we can upper bound the output $\mathrm{A}x$ as follows:

\begin{align}
\lVert \mathrm{A}x \rVert_\infty = \max_i\lvert \tilde{a}_i^\mathsf{T} x\rvert &= \max_i \left\lvert \sum_{j=1}^n a_{ij}x_j\right\rvert \\
& \leq \max_i \sum_{j=1}^n \left\lvert a_{ij} \right\rvert \left\lvert x_j\right\rvert \\
& \leq \lVert x\rVert_\infty \max_i \sum_{j=1}^n \left\lvert a_{ij} \right\rvert = M\,\lVert x\rVert_\infty
\end{align}

we thus obtain that any linear operator is bounded and continuous for $l_\infty$ in finite dimensions.