Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I know that the $p$-norm for a matrix is:

$$\|A\| = \max_{x\neq 0} \frac{\|Ax\|_p}{\|x\|_p}$$

but I don't know what this really means.

So how would I compute the $2$-norm, $3$-norm, etc for the matrix.

$$A = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}$$

UPDATE Apparently, the above matrix is too easy :) Let's try something harder.

$$A = \begin{bmatrix} 2 & 1 & 4 \\ 3 & 0 & -1 \\ 1 & 1 & 2 \end{bmatrix}$$

Thanks,

share|improve this question
    
The $2$-norm part is straightforward. Your matrix is positive definite, and its $2$-norm is equal to its largest eigenvalue. If $A$ is normal, then the $2$-norm is the largest absolute value of the eigenvalues. In general, the $2$-norm of $A$ is the positive square root of the largest eigenvalue of $A^*A$. The $1$-norm and $\infty$-norm are the most straightforward to compute directly from the entries; see en.wikipedia.org/wiki/Matrix_norm#Induced_norm. –  Jonas Meyer May 8 '11 at 23:01
    
@Jonas... I didn't mean to give a pos. def. matrix. I want to know what goes into the process of solving for the 2-norm, 3-norm, etc... of a matrix –  Hristo May 8 '11 at 23:13
    
@Hristo: I did not assume that that is all you meant. Beyond the second sentence of my comment, I never assume that the matrix is positive definite. I only commented rather than answered because I didn't have anything to say about useful methods of computing the $p$-norm when $p\not\in\{1,2,\infty\}$. –  Jonas Meyer May 8 '11 at 23:26
    
@Jonas... thanks. –  Hristo May 8 '11 at 23:29
    
@Hristo: I don't know why, but it seems that comment notifications don't work when you put "..." after "@username". –  Jonas Meyer May 8 '11 at 23:32
show 1 more comment

4 Answers

up vote 7 down vote accepted

If you have a vector $x = [x_1,x_2,\ldots,x_n]^T$ then $\|x\|_p = \sqrt[p]{|x_1|^p + |x_2|^p + \cdots |x_n|^p}$

In your case, $x = [x_1, x_2]^T$ then $Ax = [2x_1 + x_2, x_1 + 2x_2]$

$\|Ax\|_p^p = (|2x_1 + x_2|)^p + (|x_1 + 2x_2|)^p$ and $\|x\|_p^p = |x_1|^p + |x_2|^p$

$$\left( \frac{\|Ax\|_p}{\|x\|_p} \right)^p = \frac{(|2x_1 + x_2|)^p + (|x_1 + 2x_2|)^p}{|x_1|^p + |x_2|^p}$$

By symmetry, the maximum occurs when $x_1 = x_2 = y$ and hence

$$\left( \frac{\|Ax\|_p}{\|x\|_p} \right)^p = \frac{(3y)^p + (3y)^p}{y^p + y^p} = \frac{2 \times 3^p y^p}{2y^p} = 3^p$$

Hence, the $p^{th}$ norm of $A$ is $3$

For any matrix, the $2$ norm is the largest singular value.

share|improve this answer
    
@Sivaram... I made an update with a 3-by-3 matrix. Can you help out with that one? If its a bad matrix, can you show an example of this process for a non pos. def. 3-by-3 matrix? –  Hristo May 8 '11 at 23:15
    
@Hristo: What I have done works for any matrix in general. The only difference is we cannot use symmetry to conclude $x_1 = x_2$. –  user17762 May 8 '11 at 23:17
    
@Sivaram... you say "For any matrix, the 2 norm is the largest singular value." Does that hold for the 3-norm? –  Hristo May 8 '11 at 23:29
    
@Hristo: For $p \neq 1,2,\infty$, computing the matrix norm is NP-hard. Hence it is hard to say in general how to compute a general $p$ norm of a matrix. –  user17762 May 8 '11 at 23:36
    
whoa. didn't know that. thanks for the clarification. –  Hristo May 8 '11 at 23:38
add comment

As I've mentioned in this answer to an MO question, Nick Higham has made note of a numerical method he attributes to Boyd for estimating the $p$-norm of a matrix, which is essentially an approximate maximization scheme similar in flavor to the usual power method for computing the dominant eigenvalue; Higham's book has a few details, his article a few more, and then see this MATLAB implementation of the algorithm.


Code? Why sure! Here's a Mathematica translation of the MATLAB routine pnorm():

dualVector[vec_?VectorQ, p_] := 
 Module[{q = If[p == 1, Infinity, 1/(1 - 1/p)], n = Length[vec]}, 
   If[Norm[vec, Infinity] == 0, Return[vec]];
   Switch[p,
    1, 2 UnitStep[vec] - 1,
    Infinity, (Sign[Extract[vec, #]] UnitVector[n, #]) &[
     First[Flatten[Position[Abs[vec], Max[Abs[vec]]]]]],
    _, Normalize[(2 UnitStep[vec] - 1) Abs[
        Normalize[vec, Norm[#, Infinity] &]]^(p - 1), 
     Norm[#, q] &]]] /; p >= 1

Options[pnorm] = {"Samples" -> 9, Tolerance -> Automatic};

pnorm[mat_?MatrixQ, p_, opts___] := 
 Module[{q = If[p == 1, Infinity, 1/(1 - 1/p)], m, n, A, tol, sm, x, 
    y, c, s, W, fo, f, c1, s1, est, eo, z, k, th},
   {m, n} = Dimensions[mat];
   A = If[Precision[mat] === Infinity, N[mat], mat];
   {sm, tol} = {"Samples", Tolerance} /. {opts} /. Options[pnorm];
   If[tol === Automatic, tol = 10^(-Precision[A]/3)];
   y = Table[0, {m}]; x = Table[0, {n}];
   Do[
    If[k == 1, {c, s} = {1, 0},
     W = Transpose[{A[[All, k]], y}];
     fo = 0;
     Do[
      {c1, s1} = Normalize[Through[{Cos, Sin}[th]], Norm[#, p] &];
      f = Norm[W.{c1, s1}, p];
      If[f > fo,
       fo = f; {c, s} = {c1, s1}];
      , {th, 0, Pi, Pi/(sm - 1)}]
     ];
    x[[k]] = c;
    y = c A[[All, k]] + s y;
    If[k > 1, x = Join[s Take[x, k - 1], Drop[x, k - 1]]];
    , {k, n}];
   est = Norm[y, p];
   For[k = 1, True, k++,
    y = A.x;
    eo = est; est = Norm[y, p];
    z = Transpose[A].dualVector[y, p];
    If[(Norm[z, q] < z.x || Abs[est - eo] <= tol est) && k > 1, 
     Break[]];
    x = dualVector[z, q];];
   est] /; p >= 1

Now, let's use the OP's matrix as an example:

mat = N[{{2, 1, 4}, {3, 0, -1}, {1, 1, 2}}];

and check how good the estimator is in known cases:

(pnorm[ma, #] - Norm[ma, #]) & /@ {1, 2, Infinity} // InputForm
{0., -2.2045227554556845*^-6, 0.}

(i.e. the estimate for the 2-norm is good to ~ 5 digits; adjusting either Samples, Tolerance, or both would give better results).

Let's compare with Robert's example:

pnorm[ma, 4, Tolerance -> 10^-9] // InputForm
5.695759123950937

Pretty close!

Finally, here is a plot of the $p$-norm of the OP's matrix with varying $p$:

plot of p-norm of {{2, 1, 4}, {3, 0, -1}, {1, 1, 2}}

share|improve this answer
add comment

For other values of $p$, you can use Lagrange multiplier methods. Here, for example, is your $3 \times 3$ example with $p=4$ using Maple.

> M:= <<2|1|4>,<3|0|-1>,<1|1|2>>;
  X:= <x1,x2,x3>;
  MX:= M.X;
  F:= add(MX[i]^4,i=1..3)-lambda*(add(X[i]^4,i=1..3)-1);
  eqs:= {diff(F,x1),diff(F,x2),diff(F,x3),diff(F,lambda)};
  S:=RootFinding[Isolate](eqs,[x1,x2,x3,lambda]);
  pnorm:= max(map(t -> eval(lambda,t),S))^(1/4);

pnorm := 5.695759124

share|improve this answer
    
Very clever. If $p$ is not an even integer, one must also check with one variable $x_i$ set to 0, then with two $x_j, \, x_k$ set to 0, as there are absolute value signs involved. –  Will Jagy May 9 '11 at 17:58
add comment

EXTRA CREDIT: find the eigenvalues, eigenvectors, and the $1,2,\infty$ norms of the matrix $$B = \begin{pmatrix} 1 & 10 \\ -16 & 9 \end{pmatrix},$$ using the methods illustrated below. I have arranged that everything works out nicely.

ORIGINAL: I've never seen these calculated except for $p=1,2,\infty.$ Note that the 1 norm of a vector is the sum of the absolute values of the entries, while the $\infty$ norm of a vector is the largest absolute value of any entry.

As you can see from the link given by Jonas, the $\infty$ norm is the largest row sum(of absolute values), which for your 3 by 3 example is 2 + 1 + 4 = 7. This is achieved for a column vector consisting of all $\pm 1,$ where the choice of $\pm$ is made so that the product with the $2,1,4$ are all positive, so in this case all $+1. $ Take your matrix $$A = \left[\begin{matrix} 2 & 1 & 4 \\ 3 & 0 & -1 \\ 1 & 1 & 2 \end{matrix}\right],$$

$$A = \left(\begin{matrix} 2 & 1 & 4 \\ 3 & 0 & -1 \\ 1 & 1 & 2 \end{matrix}\right) \cdot \left(\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}\right) = \left(\begin{matrix} 7 \\ 2 \\ 4 \end{matrix}\right), $$ so with $$ x = \left(\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}\right), $$ we have $$ \|x\|_\infty = 1, \; \; \|Ax\|_\infty = 7, \; \; \frac{ \|Ax\|_\infty}{\|x\|_\infty} = 7, $$ and $$ \|A\|_\infty = 7. $$

The $1$ norm is the largest column sum(of absolute values), which for your 3 by 3 example is 4 + 1 + 2 = 7. This is achieved for a column vector consisting of almost all 0's and a single 1, where the choice of position for the 1 is made so that the most important column is kept. Take your matrix $$A = \left[\begin{matrix} 2 & 1 & 4 \\ 3 & 0 & -1 \\ 1 & 1 & 2 \end{matrix}\right],$$

$$A = \left(\begin{matrix} 2 & 1 & 4 \\ 3 & 0 & -1 \\ 1 & 1 & 2 \end{matrix}\right) \cdot \left(\begin{matrix} 0 \\ 0 \\ 1 \end{matrix}\right) = \left(\begin{matrix} 4 \\ -1 \\ 2 \end{matrix}\right), $$ so with $$ x = \left(\begin{matrix} 0 \\ 0 \\ 1 \end{matrix}\right), $$ we have $$ \|x\|_1 = 1, \; \; \|Ax\|_1 = 7, \; \; \frac{ \|Ax\|_1}{\|x\|_1} = 7, $$ and $$ \|A\|_1 = 7. $$

These give upper bounds for the norms of eigenvalues, working on that. From GP-Pari, largest eigenvalue is about 4.7,

? mat = [2,1,4; 3,0,-1; 1,1,2]
%1 = 
[2 1 4]

[3 0 -1]

[1 1 2]

? charpoly(mat)
%2 = x^3 - 4*x^2 - 2*x - 7
? 
? matdet(mat)
%3 = 7
? 
? polroots(  charpoly(mat)  )
%4 = [4.734676178725887352610775374 ,
 -0.3673380893629436763053876869 - 1.159101604948420124760141070*I,
 -0.3673380893629436763053876869 + 1.159101604948420124760141070*I]~
? 

I get it, the eigenvector for the real eigenvalue is given numerically as $$ x = \left(\begin{matrix} 1.803282495304177184832508716 \\ 0.9313936834217101677782666577 \\ 1 \end{matrix}\right), $$

? vec = [  1.803282495304177184832508716 , 0.9313936834217101677782666577, 1   ]
%7 = [1.803282495304177184832508716, 0.9313936834217101677782666577, 1]

? columnvec = mattranspose( vec)
%8 = [1.803282495304177184832508716, 0.9313936834217101677782666577, 1]~
? mat * columnvec
%9 = [8.537958674030064537443284089, 4.409847485912531554497526148, 4.734676178725887352610775374]~
? mat * columnvec  -   4.734676178725887352610775374  * columnvec
%10 = [4.038967835 E-28, -7.068193710 E-28, -4.038967835 E-28]~
? 
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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