1
$\begingroup$

I am going through my numerical analysis text (Epperson) and came across notation that I don't fully understand. My question is what does max refer to in this definition?

Definition $7.2$ (Matrix Norm): Let $\|\cdot\|$ be a given vector norm defined on $\mathbb{R}^n$. Define the corresponding matrix norm, for matrices $A \in \mathbb{R}^{n\times n}$, by $$\|A\| = \max_{x \neq 0}\frac{\|Ax\|}{\|x\|}$$

$\endgroup$
7
  • 1
    $\begingroup$ Can you give the exact usage in your question? $\endgroup$
    – David
    Feb 12 '17 at 16:35
  • $\begingroup$ Hi David, that's what I'm trying to figure out too... the image in the link is of the definition of a matrix norm. I'm not sure how to read the "max x != 0" term. $\endgroup$ Feb 12 '17 at 16:37
  • 1
    $\begingroup$ It's the maximum value of the expression as the vector $x$ goes through all possible values in $\mathbb{R}^n$ except $x=0$ since the denominator is not defined for this value. $\endgroup$
    – Winther
    Feb 12 '17 at 16:40
  • $\begingroup$ Thanks David for the edit. I'm going to try to wrap my head around this, I'm sure it's simpler than it seems. $\endgroup$ Feb 12 '17 at 16:56
  • $\begingroup$ @Starcrossed not a problem. The concept will be easy once you wrap your mind around it. For some norms though, it might be very hard to compute. $\endgroup$
    – David
    Feb 12 '17 at 17:09
2
$\begingroup$

This is simply the extension of a given norm to a matrix. It should be better written: $$\sup \left\{\frac{\|Ax\|}{\|x\|}: x \in \mathbb{R}^n, x\neq 0\right\} = \sup \left\{\|Ax\|:x \in \mathbb{R}^n, \|x\|=1\right\}.$$ That is, go through all normalized vectors, and see where the product $\|Ax\|$ is maximized.

-----Edit-----

As an example, let us consider the $L^1$-norm. For some matrix $A \in \mathbb{R}^n$, by definition we have that $$\|A\|_1 = \sup \left\{\|Ax\|_1:x \in \mathbb{R}^n, \|x\|_1=1\right\}.$$ Now, for a given vector $x \in R^n$, we have that $$ \displaystyle\|Ax\|_1 = \left\|\begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{pmatrix}\cdot \begin{pmatrix} x_1\\ x_2\\ \vdots\\ x_n \end{pmatrix}\right\|_1 = \left\|\begin{pmatrix} \sum_{j=1}^na_{1j}x_j\\ \sum_{j=1}^na_{2j}x_j\\ \vdots\\ \sum_{j=1}^na_{nj}x_j \end{pmatrix}\right\|_1 = \sum_{i=1}^n\left|\sum_{j=1}^na_{ij}x_j\right|.$$ Thus, we can write the $L^1$-norm of $A$ as $$\displaystyle \|A\|_1 = \sup_{\|x\|=1}\left\{\sum_{i=1}^n\left|\sum_{j=1}^na_{ij}x_j\right|\right\}.$$ We can bound this in the following way, $$\|A\|_1 \leq \sup_{\|x\|=1}\left\{\sum_{i=1}^n\sum_{j=1}^n\left|a_{ij}x_j\right|\right\} = \sup_{\|x\|=1}\left\{\sum_{j=1}^n\left|x_j\right|\sum_{i=1}^n\left|a_{ij}\right|\right\}.$$ Now, consider the fact that $$\displaystyle \sum_{j=1}^n\left|x_j\right|\sum_{i=1}^n\left|a_{ij}\right| \leq \sum_{j=1}^n\left|x_j\right|\max_{1\leq j \leq n}\left\{\sum_{i=1}^n\left|a_{ij}\right|\right\} = \|x\|_1\cdot \max_{1\leq j \leq n}\left\{\sum_{i=1}^n\left|a_{ij}\right|\right\}.$$ Now, since our matrix norm is only concerned with normalized vectors, we have clearly that $$\displaystyle \|A\|_1 \leq \sup_{\|x\|=1}\left\{\|x\|_1\cdot \max_{1\leq j \leq n}\left\{\sum_{i=1}^n\left|a_{ij}\right|\right\}\right\} = \max_{1\leq j \leq n}\left\{\sum_{i=1}^n\left|a_{ij}\right|\right\}.$$ Therefore, we have an upper bound. But this upper bound is clearly attainable, we simply take the $j^*$ corresponding to the column we are maximizing over in the previous equation, and let $x_{j^*} = 1, x_i = 0$ ($i \neq j^*$). Thus, the $L^1$-norm for a matrix is simply the maximum of the absolute column sums. So, as you see, the definition may be readily understood, but determining the value of the norm may be less so. And, in many cases, a closed form of the norm doesn't exist, and so you need to numerically solve the optimization (maximization) problem for each given $A$.

$\endgroup$
1
$\begingroup$

The "max" refers to the maximum of the set of numbers $\{\frac{\Vert Ax \Vert}{\Vert x \Vert } , 0\neq x\in \mathbb{R}^n\}$. Note that since this is a set of norms on vectors, then it's a set of non negative numbers.

$\endgroup$
2
  • $\begingroup$ Aha okay I think I get it now... basically we are finding a vector x such that we are maximizing the norm, right? $\endgroup$ Feb 12 '17 at 17:00
  • $\begingroup$ Yes. Just note that we're looking for an $x$ that maximizes the quotient of the norms $\frac{ \Vert Ax \Vert }{ \Vert x \Vert }$ $\endgroup$
    – NSA
    Feb 13 '17 at 9:23
0
$\begingroup$

It means the maximum of the quantity

$$\frac{||Ax||}{||x||}$$

along all the vectors $x\in\mathbb{R}^n$ that are not zero.

$\endgroup$
5
  • $\begingroup$ Thanks Smurf... So to further understand, suppose we are given only one vector x for a linear expression Ax = b, then that vector alone would be the only possible vector to use in finding the max, right? $\endgroup$ Feb 12 '17 at 16:45
  • $\begingroup$ No, the norm of the matrix is defined as above. If you have an expression $Ax=b$ you still should use the maximum along every $x\neq 0$. $\endgroup$
    – Smurf
    Feb 12 '17 at 16:47
  • $\begingroup$ I'm sure it is probably trivially simple to you so I apologize in advance for this dumb question ... wouldn't every max x ≠ 0 in ℝn be infinitely large? $\endgroup$ Feb 12 '17 at 16:55
  • $\begingroup$ Notice that while it may seem that if you pick and arbitrary large $x$, the numerator increases, so does the denominator. So one "controls" the other and the maximum exists (this has to be proven, I am just giving you the idea of why it works). $\endgroup$
    – Smurf
    Feb 12 '17 at 17:16
  • $\begingroup$ @Starcrossed, when the space is infinite dimensional, the quotient can be unbounded. $\endgroup$ Mar 8 '17 at 10:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.