Definition of matrix norm induced by vector $p$-norm

Question

I'm having a bit of trouble understanding the exact definition of a matrix norm that is induced by the vector norm. In this specific case, our matrix norm definition is: $$||A|| = \max\limits_{x \neq 0}\frac{||Ax||}{||x||}$$ My textbook defines them for $p = 1, \infty$, but says that $2$ and others are difficult to compute. My question is what exactly does this definition mean? $||Ax||$ and $||x||$ are both scalars, so what does the $\max$ signify?. The textbook defines the functions as below: $$||x||_p = (\sum\limits_{i=1}^{n}|x_i|^p)^\frac{1}{p}$$ Suppose our matrix and vectors are below and $p$ = 1: $$||A||_1 = \max\limits_{x \neq 0}\frac{||Ax||_1}{||x||_1}\\ ||Ax||_1 = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix}\begin{bmatrix}x_1 \\ x_2 \\ x_3\end{bmatrix} = \begin{bmatrix} a_{11}x_1 & a_{12}x_2 & a_{13}x_3 \\ a_{21}x_1 & a_{22}x_2 & a_{23}x_3 \\ a_{31}x_1 & a_{32}x_2 & a_{33}x_3 \end{bmatrix}\\ = x_1(a_{11} + a_{21} + a_{31}) + x_2(a_{21} + a_{22} + a_{23}) + x_3(a_{31}+a_{32}+a_{33})\\[0.1in] \text{and for x we have}\\ ||x||_1 = x_1 + x_2 + x_3$$ So then the division of these are just scalars, but clearly I'm missing something from the definition (i.e. $\max$ means what?). Also is that the book has an equivalence of that $|A|_1$ is equal to the maximum column sum of the matrix $A$, but my calculation does not lead to that. Can someone enlighten me on what it is I'm missing from this?

Answer 1

To simplify the definition let us begin with a simple example : $$ A=\left( \begin{array}{ccc} 1 & 0 & 0\\ 0 & 2 & 0 \\ 0&0&5 \end{array} \right) $$ Let $X=(x,y,z)\in\mathbb{R}^3$ so $AX=(x,2y,5z)$, $\|X\|=|x|+|y|=|z|$ and $\|AX\|=|x|+|2y|+|5z|$ it's obvious that $f(x,y,z)=\|AX\|/\|X\|$ is a function of $X=(x,y,z)$ for example $f(1,1,0)=3$ and $f(0,0,1)=5$ etc

But we can see that :

$$ 0\leq f(x,y,z)\leq 5 \qquad \forall (x,y,z)\in \mathbb{R}^3 \textrm{ such that } |x|+|y|+|z|\ne 0 $$

In fact : the first inequality is trivial because the norm is non-negative, for the second $$ 5-f(x,y,z)=5-\frac{|x|+2|y|+5|z|}{|x|+|y|+|z|}=\frac{4|x|+3|y|}{|x|+|y|+|z|}\geq 0 $$ and the maximum of $\|AX\|/\|X\|$ is $5$ [ $X=(0,0,1)$ it's calculated up her] (and remark that $5$ is equal to the maximum column sum of the matrix $A$)

For general cases not as your calculation the function $f$ is : $$ f(x,y,z)=\frac{ |a_{11}x + a_{12}y + a_{13}z|+|a_{21}x + a_{22}y + a_{23}z|+|a_{31}x + a_{32}y + a_{33}z|}{|x|+|y|+|z|} $$ If we put $\alpha$ is the maximum column sum of the matrix $A$ for example $\alpha=|a_{13}|+|a_{23}|+|a_{33}|$ :

$$ 0\leq f(x,y,z)\leq \alpha \qquad \forall (x,y,z)\in \mathbb{R}^3 \textrm{ such that } |x|+|y|+|z|\ne 0 $$

In fact : the first inequality is trivial because the norm is non-negative, for the second \begin{eqnarray} \alpha-f(x,y,z)&=& \alpha-\frac{|a_{11}x + a_{12}y + a_{13}z|+|a_{21}x + a_{22}y + a_{23}z|+|a_{31}x + a_{32}y + a_{33}z|}{|x|+|y|+|z|}\\ &\geq & \alpha-\frac{|x|(|a_{11}|+|a_{21}| +|a_{31}| ) +|y|(|a_{12}| + |a_{22}|+|a_{32}|)+|z|( |a_{13}|+|a_{23}|+|a_{33}|)}{|x|+|y|+|z|} \\ &=&\frac{|x|(\alpha -(|a_{11}|+|a_{21}| +|a_{31}|) ) +|y|(\alpha-(|a_{12}| + |a_{22}|+|a_{32}|))}{|x|+|y|+|z|} \geq 0 \end{eqnarray}

and the maximum of $\|AX\|/\|X\|$ is $\alpha$ [ $X=(0,0,1)$ ] So $$ \|A\|_1=\sup_{\|X\|\ne 0} \frac{\|AX\|}{\|X\|}=\alpha $$