1
$\begingroup$

Compute the condition number of the matrix $B$ :

$$ B=\begin{bmatrix}3&7&1\\5&8&0\\6&3&2\end{bmatrix} $$ in terms of $\|\cdot\|_{1}$ and $\|\cdot\|_{\infty}$.

Important: Our definition of the condition number:

Consider a linear map $A : X \rightarrow Y $, then we define the condition number as follows: $$C(A) = \frac{\sup\limits_{x \in X, \|x\|_X=1} \|Ax\|_Y}{\inf\limits_{x \in X, \|x\|_X=1} \|Ax\|_Y}$$ with $\|\cdot\|_X$ and $\|\cdot\|_Y$.

So I've read that if $A \in \operatorname{isometry}(X,Y)$ then $C(A) = \|A\|_{L(X,Y)} \|A^{-1}\|_{L(Y,X)}$ with $L(X,Y)$. Do I have to use this? And if I have to use $C(A) = \|A\|_{L(X,Y)} \|A^{-1}\|_{L(Y,X)}$, can you explain what $L(X,Y)$ and $L(Y,X)$ are in this exercise?

$\endgroup$
  • 1
    $\begingroup$ Please type $3\times 3$ for $3\times 3$ instead of 3 $\times$ 3 for 3 $\times$ 3 because, after all, $3$ is a mathematical symbol. $\endgroup$ – Shaun Jun 30 '18 at 11:33
  • $\begingroup$ $L(X,Y)$ is the vector space of linear maps from $X$ to $Y$; in this case $X=Y = \mathbb{R}^3$ of course. If $X$ and $Y$ have norms (as is common) then $L(X,Y)$ carries the so-called operator norm, usually: $\|A\|_{L(X,Y)} = \sup \{\{\|Ax\|_Y : x \in X, \|x\|_X = 1 \}$ $\endgroup$ – Henno Brandsma Jun 30 '18 at 11:58
  • 1
    $\begingroup$ @JackJ. It is good that you try to improve posts by suggesting edits. However, it would be great if you would make your suggestions more thorough. Take a look at Xander Henderson's edit here for inspiration. $\endgroup$ – Daniel Fischer Jun 30 '18 at 19:16
  • $\begingroup$ @ Daniel Fischer♦ Thank you. I will do it! $\endgroup$ – Jack J. Jun 30 '18 at 19:23
2
$\begingroup$

Let us compute for the $L^1$-norm. All "modules" applied on a vector $$ x=\begin{bmatrix}a\\b\\c\end{bmatrix} \ne 0$$ reflect the $1$-norm for a while.

Then $$ \begin{aligned} \sup_{|x|=1}|Bx| &=\sup_{x\ne 0}\frac{|Bx|}{|x|} \\ &=\sup_{(a,b,c)\ne 0}\frac{|3a+7b+c|+|5a+8b|+|6a+3b+2c|}{|a|+|b|+|c|} \\ &\le \sup_{(a,b,c)\ne 0} \frac {3|a|+7|b|+|c|+5|a|+8|b|+6|a|+3|b|+2|c|} {|a|+|b|+|c|} \\ &= \sup_{(a,b,c)\ne 0} \frac {14|a|+18|b|+3|c|} {|a|+|b|+|c|} \\ \\ &\le \sup_{(a,b,c)\ne 0} \frac {18|a|+18|b|+18|c|} {|a|+|b|+|c|} \\ &=18\ . \end{aligned} $$ And the value $18$ is taken for $(0,1,0)$. Note that we are taking the maximal value for the sum of the modules of the column entries of the given matrix, this is the second column, the result is $\max(3+5+6, \ 7+8+3,\ 1+0+2)=18$. For the infimum... Let $C$ be the matrix $$ C = B^{-1} =\begin{bmatrix}3&7&1\\5&8&0\\6&3&2\end{bmatrix}^{-1} =\frac 1{55} \begin{bmatrix} -16 & 11 & 8 \\ 10 & 0 & -5 \\ 33 & -33 & 11 \end{bmatrix} \ . $$ Then $$ \begin{aligned} \inf_{|x|=1}|Bx| &=\inf_{x\ne 0}\frac{|Bx|}{|x|} \\ &\qquad\text{Substitution: $Bx=y$...} \\ &=\inf_{y\ne 0}\frac{|y|}{|Cy|} \\ &=\left(\sup_{y\ne 0}\frac{|Cy|}{|y|}\right)^{-1} \\ &=\left(\max\ \left(\ \frac 1{55}(16+10+33),\ \frac 1{55}(11+0+33),\ \frac 1{55}(8+5+11),\ \right)\ \right)^{-1} \\ &=\left(\frac{59}{55}\right)^{-1} =\frac{55}{59}\approx 0.932203389830508\dots \ . \end{aligned} $$ We have only to take the quotient now, $$ C(B)=\frac{18}{55/59}= \frac {1065}{55}\approx 19.3090909090\dots\ . $$


Same game for the $\infty$-norm. All "modules" on a non-zero vector are denoting in the following this norm. $$ \begin{aligned} \sup_{|x|=1}|Bx| &=\sup_{\substack{x=(a,b,c)^T\\|a|,|b|,|c|\le 1}}|Bx| \\ &=\sup_{|a|,|b|,|c|\le 1}\max(\ |3a+7b+c|,\ |5a+8b|,\ |6a+3b+2c|\ ) \\ &\le \sup_{|a|,|b|,|c|\le 1}\max(\ 3+7+1,\ 5+8,\ 6+3+2\ ) \\ &=\max(\ 3+7+1,\ 5+8,\ 6+3+2\ )=13\ . \end{aligned} $$ This time we are taking the maximal value of the sums of the absolute values on the rows. The second row won. The maximum is taken for $a=b=c=1$.

For the infimum value, we pass again to $C=B^{-1}$, the corresponding supremum is $\frac 1{55}(33+33+11)=\frac 15(3+3+1)=\frac 75$, so the infimum needed for $B$ is its inverse, $$\frac 57\approx 0.\,714285\,714285\dots\ $$ So $$ C(B) = \frac{13}{5/7}=\frac{91}5=18.2 \ . $$


Computer simulation. This experience should not be underestimated. It is often important to be able to check in a second such results. Here using sage:

Code:

import random
sup1, inf1, supoo, infoo = 0, oo, 0, oo    # init, we will make some of them bigger, the other smaller...

n1  = lambda  a,b,c:         abs(a) + abs(b) + abs(c)
noo = lambda  a,b,c:    max( abs(a) , abs(b) , abs(c) )

B = matrix(QQ, 3, 3, [3,7,1, 5,8,0, 6,3,2] )

for trial in xrange(10**6):
    a, b, c = [ random.uniform(-1,1) for _ in (1,2,3) ]
    s, t, u = B*vector( [a,b,c] )

    norm1 = n1( s,t,u ) / n1( a,b,c )
    if norm1 > sup1:    sup1 = norm1
    if norm1 < inf1:    inf1 = norm1

    normoo = noo( s,t,u ) / noo( a,b,c )
    if normoo > supoo:    supoo = normoo
    if normoo < infoo:    infoo = normoo

print "1-norm:", sup1, inf1, sup1/inf1
print "oo-norm:", supoo, infoo, supoo/infoo

Results this time:

1-norm: 17.9935919413 0.936889759239 19.2056661564
oo-norm: 12.9999942319 0.716228500506 18.1506240295
$\endgroup$
  • $\begingroup$ Thanks, i am correcting it! $\endgroup$ – dan_fulea Jul 1 '18 at 12:16

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.