Norm Inequalities in Matrix Multiplication

35 Views Asked by At

Consider $B\in \mathbb{R}^{m\times h}$ and $A \in \mathbb{R}^{h\times n}$. We can make sense of \begin{align*} \lVert BA\rVert_{1,\infty} = \sup_{\{x \in \mathbb{R}^n:\lVert x\rVert_1 = 1\}}\lVert BAx\rVert_{\infty} \end{align*} and we know \begin{align*} \lVert BA\rVert_{1,\infty} \leq \lVert B\rVert_{1}\lVert A\rVert_{1,\infty} \end{align*} Now, let $a = \lVert A\rVert_{1,\infty}$ and Consider \begin{align*} BA = (aB)(a^{-1}A) \end{align*} Let $k$ be an integer such that $k^{-1}a\lVert B\rVert_1 < 1$ and define $\tilde{B} = k^{-1}aB$ and $\tilde{A} = a^{-1}A$. Then \begin{align*} BA &=(aB)(a^{-1}A)\\ &=k\tilde{B}\tilde{A}\\ &=(\tilde{B} + \cdots +\tilde{B})\tilde{A}\\ &=\begin{bmatrix} \tilde{B} & \cdots & \tilde{B} \end{bmatrix}\begin{bmatrix} \tilde{A} \\ \vdots \\ \tilde{A} \end{bmatrix} \end{align*} Moreover, \begin{align*} \Big\lVert\begin{bmatrix} \tilde{B} & \cdots & \tilde{B} \end{bmatrix} \Big\rVert_{1} < 1 \end{align*} because it it is the maximum column sum of absolute values and this is just the same as that of one $\tilde{B}$ which by construction satisfies $<1$. Similarly, we have \begin{align*} \Bigg\lVert\begin{bmatrix} \tilde{A} \\ \vdots \\\tilde{A} \end{bmatrix} \Bigg\rVert_{1,\infty} &= \sup_{\{x \in \mathbb{R}^n:\lVert x\rVert_1 = 1\}}\Bigg\lVert\begin{bmatrix} \tilde{A} \\ \vdots \\\tilde{A} \end{bmatrix}x \Bigg\rVert_{\infty}\\ &=\sup_{\{x \in \mathbb{R}^n:\lVert x\rVert_1 = 1\}}\Bigg\lVert\begin{bmatrix} \tilde{A}x \\ \vdots \\\tilde{A}x \end{bmatrix} \Bigg\rVert_{\infty}\\ &\sup_{\{x \in \mathbb{R}^n:\lVert x\rVert_1 = 1\}}\lVert \tilde{A}x \rVert_{\infty}\\ &= \lVert \tilde{A}\rVert_{1,\infty} \end{align*} which is $1$ by construction. Then \begin{align*} \lVert BA\rVert_{1,\infty} &= \Bigg\lVert\begin{bmatrix} \tilde{B} & \cdots & \tilde{B} \end{bmatrix}\begin{bmatrix} \tilde{A} \\ \vdots \\ \tilde{A} \end{bmatrix}\Bigg\rVert_{1,\infty}\\ &\leq \Big\lVert\begin{bmatrix} \tilde{B} & \cdots & \tilde{B} \end{bmatrix} \Big\rVert_{1} \Bigg\lVert\begin{bmatrix} \tilde{A} \\ \vdots \\\tilde{A} \end{bmatrix} \Bigg\rVert_{1,\infty}\\ & < 1 \end{align*} But this cant be right for arbitrary $A,B$. Where did i go wrong?