norms and vectors

**awaisysf** · December 15th 2009, 06:41 AM

The 'T' means transposed.

Consider the four non-zero COLUMN vectors in R^2:
x=[x1, x2]; y=[y1, y2]; w=[w1, w2]; z=[z1, z2]

Let xTw=0, yTz=0, A=xyT, B=wzT

Determine:

a) The 2-norm of A
b) The singular value decomposition (SVD) of A
c) The Range space and Nullspace of A
d) The pseudo-inverse de A
e) The singular value decomposition (SVD) of A+B

**abender** · December 16th 2009, 11:11 AM

The 'T' means transposed.

Consider the four non-zero COLUMN vectors in R^2:
x=[x1, x2]; y=[y1, y2]; w=[w1, w2]; z=[z1, z2]

Let xTw=0, yTz=0, A=xyT, B=wzT

Determine:

a) The 2-norm of A
b) The singular value decomposition (SVD) of A
c) The Range space and Nullspace of A
d) The pseudo-inverse de A
e) The singular value decomposition (SVD) of A+B

--------------------------------------------------------
$x^Tw = \begin{bmatrix}x_1 & x_2\end{bmatrix} \begin{bmatrix}w_1 \\ w_2 \end{bmatrix} = \begin{bmatrix}x_1 w_1 + x_2 w_2\end{bmatrix}=0 $

$y^Tz = \begin{bmatrix}y_1 & y_2 \end{bmatrix} \begin{bmatrix}z_1 \\ z_2 \end{bmatrix} = \begin{bmatrix}y_1 z_1 + y_2 z_2 \end{bmatrix} =0 $

$A = xy^T = \begin{bmatrix}x_1 \\ x_2 \end{bmatrix} \begin{bmatrix}y_1 & y_2 \end{bmatrix} = \begin{bmatrix}x_1 y_1 & x_1 y_2 \\ x_2 y_1 & x_2 y_2\end{bmatrix} $

$B = wz^T = \begin{bmatrix}w_1 \\ w_2 \end{bmatrix} \begin{bmatrix}z_1 & z_2 \end{bmatrix} = \begin{bmatrix}w_1 z_1 & w_1 z_2 \\ w_2 z_1 & w_2 z_2\end{bmatrix} $

PART A:

$\vert\vert A \vert\vert_2 = \sqrt{\lambda_{max}(A^H A)}$ , whereby $A^H$ is the conjugate transpose of $A$ .

$A = \begin{bmatrix}x_1 y_1 & x_1 y_2 \\ x_2 y_1 & x_2 y_2\end{bmatrix}$

$A^T = \begin{bmatrix}x_1 y_1 & x_2 y_1 \\ x_1 y_2 & x_2 y_2\end{bmatrix}$

$A^H \equiv \bar{A}^T = A^T =\begin{bmatrix}x_1 y_1 & x_2 y_1 \\ x_1 y_2 & x_2 y_2\end{bmatrix}$

(Note that since each of the entries in $A^T \text{ are real, } A^H \text{ can simply be written here as }A^T$ ).

-------
EDIT: I feel like I owe more of an explanation for why $\bar{A}^T = A^T$ in this problem. $\bar{A}^T$ is called the conjugate transpose matrix of $A$ because each entry in $\bar{A}^T$ is the complex conjugate (remember from algebra?) of its respective entry (i.e., same location in the matrix) in $A^T$ . In our case, since $x_1,x_2,y_1,y_2 \in$ R, the entries in $A^T$ and $\bar{A}^T$ are identical; $\bar{A}^T = A^T$ .
--------

So,

$A^H A = A^T A =\begin{bmatrix}x_1 y_1 & x_2 y_1 \\ x_1 y_2 & x_2 y_2\end{bmatrix} \begin{bmatrix}x_1 y_1 & x_1 y_2 \\ x_2 y_1 & x_2 y_2\end{bmatrix} = \begin{bmatrix}x_1^2 y_1^2 + x_2^2 y_1^2 & x_1^2 y_1 y_2 + x_2^2 y_1 y_2 \\ x_1^2 y_1 y_2 + x_2^2 y_1 y_2 & x_1^2 y_2^2 + x_2^2 y_2^2 \end{bmatrix} = $ $ \begin{bmatrix} y_1^2 (x_1^2 + x_2^2) & y_1 y_2 (x_1^2 + x_2^2) \\ y_1 y_2 (x_1^2 + x_2^2) & y_2^2 (x_1^2 + x_2^2) \end{bmatrix}$

Now, we compute our characteristic polynomial, which will give us what we need to know in terms of eigenvalues.

$\det(A^H A - \lambda I) = \det\begin{bmatrix} y_1^2 (x_1^2 + x_2^2) - \lambda& y_1 y_2 (x_1^2 + x_2^2) \\ y_1 y_2 (x_1^2 + x_2^2) & y_2^2 (x_1^2 + x_2^2) - \lambda \end{bmatrix} = 0$

$\implies \big{(}y_1^2 (x_1^2 + x_2^2) - \lambda \big{)} \big{(}y_2^2 (x_1^2 + x_2^2) - \lambda \big{)} - \big{(}y_1 y_2 (x_1^2 + x_2^2) \big{)} \big{(}y_1 y_2 (x_1^2 + x_2^2) \big{)} $

$\implies y_1^2 y_2^2 (x_1^2 + x_2^2)^2 - \lambda y_1^2(x_1^2 + x_2^2) - \lambda y_2^2(x_1^2 + x_2^2) + \lambda^2 - y_1^2 y_2^2 (x_1^2 + x_2^2)^2 = 0$

$\implies -\lambda y_1^2(x_1^2 + x_2^2) - \lambda y_2^2(x_1^2 + x_2^2) + \lambda^2 = 0$

$\implies \lambda^2 - \lambda y_1^2 (x_1^2 + x_2^2) - \lambda y_2^2 (x_1^2 + x_2^2) = 0 $

$\implies \lambda^2 - \lambda y_1^2 (x_1^2 + x_2^2) - \lambda y_2^2 (x_1^2 + x_2^2) = 0 $

$\implies \lambda^2 - \lambda \big{(} (y_1^2 (x_1^2 + x_2^2) + y_2^2 (x_1^2 + x_2^2)\big{)} = 0 $

$\implies \big{(}\lambda \big{)} \big{(} \lambda - \big{(} y_1^2 (x_1^2 + x_2^2) + y_2^2 (x_1^2 + x_2^2)\big{)} = 0 $

$\implies \big{(}\lambda \big{)} \big{(} \lambda - (y_1^2 + y_2^2) (x_1^2 + x_2^2)\big{)} = 0 $

Sooooooooooo,

$\lambda_1 = 0,$
$\lambda_2 = (x_1^2 + x_2^2) (y_1^2 + y_2^2)$

The greatest of these two roots, is of course, $lambda_2 = (x_1^2 + x_2^2) (y_1^2 + y_2^2)$ , since it absolutely must be positive by virtue of the fact that both x and y are given as non-zero column vectors, and addition and multiplication of positive real numbers will never give a negative result.

-------------------

So FINALLY, we compute the 2-norm of $A$ :

$\indent \vert\vert A \vert\vert_2 = \sqrt{\lambda_{max}(A^H A)} = \sqrt{(x_1^2 + x_2^2) (y_1^2 + y_2^2)}$

This problem is the pinnacle of tedium.
-Andy

**abender** · December 16th 2009, 07:43 PM

PART B:

The SVD of an $m$ by $n$ matrix is written $A_{mn} = U_{mm} S_{mn} V_{nn}^T$ , whereby $U^T U = I, V^T V = I,$ the columns of $U$ are orthogonal eigenvectors of $AA^T$ , the columns of $V$ are orthogonal eigenvectors of $A^T A$ , and $S$ is a diagonal matrix containing the square roots of eigenvalues from $U$ or $V$ in descending order.

$A = \begin{bmatrix}x_1 y_1 & x_1 y_2 \\ x_2 y_1 & x_2 y_2 \end{bmatrix}$

$A^T = \begin{bmatrix}x_1 y_1 & x_2 y_1 \\ x_1 y_2 & x_2 y_2 \end{bmatrix}$

$A^T A = \begin{bmatrix} y_1^2 (x_1^2 + x_2^2) & y_1 y_2 (x_1^2 + x_2^2) \\ y_1 y_2 (x_1^2 + x_2^2) & y_2^2 (x_1^2 + x_2^2) \end{bmatrix}$

$AA^T = \begin{bmatrix} x_1 y_1 & x_1 y_2 \\ x_2 y_1 & x_2 y_2 \end{bmatrix} \begin{bmatrix}x_1 y_1 & x_2 y_1 \\ x_1 y_2 & x_2 y_2 \end{bmatrix} = \begin{bmatrix} x_1^2 y_1^2 + x_1^2 y_2^2 & x_1 x_2 y_1^2 + x_1 x_2 y_2^2 \\ x_1 x_2 y_1^2 + x_1 x_2 y_2^2 & x_2^2 y_1^2 + x_2^2 y_2^2 \end{bmatrix} =$ $\begin{bmatrix} x_1^2 (y_1^2 + y_2^2) & x_1 x_2 (y_1^2 + y_2^2) \\ x_1 x_2 (y_1^2 + y_2^2) & x_2^2 (y_1^2 + y_2^2) \end{bmatrix}$

EIGENVECTORS of $AA^T$ :

$\indent \begin{bmatrix} x_1^2 (y_1^2 + y_2^2) & x_1 x_2 (y_1^2 + y_2^2) \\ x_1 x_2 (y_1^2 + y_2^2) & x_2^2 (y_1^2 + y_2^2) \end{bmatrix} \begin{bmatrix} \alpha \\ \beta \end{bmatrix} = \lambda \begin{bmatrix} \alpha \\ \beta \end{bmatrix}$

(Eq. 1) $\indent x_1^2 (y_1^2 + y_2^2)\alpha + x_1 x_2 (y_1^2 + y_2^2)\beta = \lambda \alpha$
(Eq. 2) $\indent x_1 x_2 (y_1^2 + y_2^2)\alpha + x_2^2 (y_1^2 + y_2^2)\beta = \lambda \beta$

Rearranging (Eq. 1):

$ x_1^2 (y_1^2 + y_2^2) \alpha + x_1 x_2 (y_1^2 + y_2^2) \beta - \lambda \alpha = 0$ $ \implies \bigg{(}\big{(} x_1^2 (y_1^2 + y_2^2)\big{)}-\lambda\bigg{)}\alpha + x_1 x_2 (y_1^2 + y_2^2)\beta = 0$

Rearranging (Eq. 2):

$x_1 x_2 (y_1^2 + y_2^2)\alpha + x_2^2 (y_1^2 + y_2^2)\beta - \lambda \beta =0$ $ \implies x_1 x_2 (y_1^2 + y_2^2)\alpha + \bigg{(}\big{(} x_2^2 (y_1^2 + y_2^2)\big{)} - \lambda \bigg{)}\beta =0$

Now we solve for $\lambda$ by setting the determinant of the coefficient matrix equal to 0:

$ \det \begin{bmatrix} \big{(} x_1^2 (y_1^2 + y_2^2)\big{)}-\lambda & x_1 x_2 (y_1^2 + y_2^2) \\ x_1 x_2 (y_1^2 + y_2^2) & \big{(} x_2^2 (y_1^2 + y_2^2)\big{)} - \lambda \end{bmatrix} = 0$

We now set up the characteristic equation. Solving for $\lambda$ will give us our eigenvalues.

$ \bigg{(} \big{(} x_1^2 (y_1^2 + y_2^2) \big{)} - \lambda \bigg{)} \bigg{(} \big{(} x_2^2 (y_1^2 + y_2^2)\big{)} - \lambda \bigg{)} - \big{(} x_1 x_2 (y_1^2 + y_2^2) \big{)}$ $ \big{(} x_1 x_2 (y_1^2 + y_2^2) \big{)} - x_1^2 x_2^2 (y_1^2 + y_2^2)^2 = 0$

$\implies x_1^2 x_2^2 (y_1^2 + y_2^2)^2 - \lambda x_1^2 (y_1^2 + y_2^2) - \lambda x_2^2 (y_1^2 + y_2^2) + \lambda^2 - x_1^2 x_2^2 (y_1^2 + y_2^2)^2 = 0$

$\implies \lambda^2 - \lambda x_1^2 (y_1^2 + y_2^2) - \lambda x_2^2 (y_1^2 + y_2^2) = 0 $

$\implies \lambda^2 - \lambda \big{(} x_1^2 (y_1^2 + y_2^2) + x_2^2 (y_1^2 + y_2^2)\big{)} = 0$

$\implies \lambda^2 - \lambda \big{(}(x_1^2 + x_2^2)(y_1^2 + y_2^2)\big{)} = 0 $

$\implies \big{(}\lambda\big{)}\big{(}\lambda - (x_1^2 + x_2^2)(y_1^2 + y_2^2)\big{)} = 0$

Therefore, the eigenvalues of $AA^T$ are:

$\lambda_1 = 0$
$\lambda_2 = (x_1^2 + x_2^2)(y_1^2 + y_2^2)$

Now we plug $\lambda$ back in to the original equations to get our eigenvectors.

For $\lambda = 0$ , we get

$x_1^2 (y_1^2 + y_2^2)\alpha + x_1 x_2 (y_1^2 + y_2^2)\beta = 0$

$x_1 x_2 (y_1^2 + y_2^2)\alpha + x_2^2 (y_1^2 + y_2^2)\beta =0$

An appropriate choice is $\alpha = x_2$ ,
and $\beta = -x_1$ . Thus, we have the eigenvector $[x_2, -x_1]$ corresponding to the eigenvalue $\lambda = 0$

For $\lambda = (x_1^2 + x_2^2)(y_1^2 + y_2^2)$ , we have

$\bigg{(}\big{(} x_1^2 (y_1^2 + y_2^2)\big{)}-(x_1^2 + x_2^2)(y_1^2 + y_2^2)\bigg{)}\alpha + x_1 x_2 (y_1^2 + y_2^2)\beta = 0$

$x_1 x_2 (y_1^2 + y_2^2)\alpha + \bigg{(}\big{(} x_2^2 (y_1^2 + y_2^2)\big{)} - (x_1^2 + x_2^2)(y_1^2 + y_2^2) \bigg{)}\beta =0$

In both equations, we can cancel out a common factor, namely, $(y_1^2 + y_2^2)$ . The equations become

$\bigg{(}\big{(} x_1^2 \big{)}-(x_1^2 + x_2^2)\bigg{)}\alpha + x_1 x_2 \beta = (-x_2^2)\alpha + x_1 x_2 \beta = 0$

$x_1 x_2 \alpha + \bigg{(}\big{(} x_2^2 \big{)} - (x_1^2 + x_2^2) \bigg{)}\beta = x_1 x_2 \alpha - x_1^2 \beta = 0$

We now want to find appropriate values for $\alpha$ and $\beta$ , using the equations.

$(-x_2^2)\alpha + x_1 x_2 \beta = x_1 x_2 \beta - x_2^2 \alpha = x_2 (x_1 \beta - x_2 \alpha ) = 0 \implies (x_1 \beta - x_2 \alpha ) = 0$

$x_1 x_2 \alpha - x_1^2 \beta = x_1 (x_2 \alpha - x_1 \beta) =0 \implies (x_2 \alpha - x_1 \beta) = 0$

Since $(x_2 \alpha - x_1 \beta) = (x_2 \alpha - x_1 \beta) = 0$ ,

$\alpha = x_1$
$\beta = x_2$ .

Thus, we have the eigenvector $[x_1, x_2]$ corresponding to the eigenvalue $/lambda = (x_1^2 + x_2^2)(y_1^2 + y_2^2)$ .

[more to go]

**Isomorphism** · December 16th 2009, 08:52 PM

Originally Posted by awaisysf

The 'T' means transposed.

Consider the four non-zero COLUMN vectors in R^2:
x=[x1, x2]; y=[y1, y2]; w=[w1, w2]; z=[z1, z2]

Let xTw=0, yTz=0, A=xyT, B=wzT

Determine:

a) The 2-norm of A

There is an easier way using the definition directly:
I will assume all norms here as 2 norms.

Definition: $||A|| = \text{sup} \, \frac{||Az||}{||z||}$ where vector $z$ is varied over all non zero vectors.

Proof: So using the definition $\frac{||xy^Tz||}{||z||} = \left|y^T\left(\frac{z}{||z||}\right)\right|||x||$

We have to maximise the right hand side expression and this can be done by choosing z along y and thus $z = \alpha y$ for some real $\alpha$ . Substituting $z$ in,
$||A|| = \text{sup} \, y^T\left(\frac{z}{||z||}\right)||x|| = ||y|| ||x||$

**Isomorphism** · December 16th 2009, 10:44 PM

Originally Posted by awaisysf

The 'T' means transposed.

Consider the four non-zero COLUMN vectors in R^2:
x=[x1, x2]; y=[y1, y2]; w=[w1, w2]; z=[z1, z2]

Let xTw=0, yTz=0, A=xyT, B=wzT

Determine:
b) The singular value decomposition (SVD) of A

To obtain SVD of A, first it suffices to obtain orthogonal eigenvectors of $AA^T$ and $A^TA$ .

$AA^T = (xy^T)(yx^T) = ||y||^2 xx^T$
$A^TA = (yx^T)(xy^T) = ||x||^2 yy^T$

By observation it is clear that $x$ is an eigenvector for $AA^T$ and the eigenvalue for that is $||x||^2||y||^2$ . Since rank of $xx^T$ is 1, the other eigenvalue $AA^T$ is 0 and $w$ is an eigenvector corresponding to 0 eigenvalue. Also x and w are orthogonal. So we have obtained our spectral decomposition for $AA^T$

Let $U = \left[ \begin{array}{cc}\frac{x}{||x||} & \frac{w}{||w||}\end{array}\right]$ and $\Sigma = \left[ \begin{array}{cc}||x||\, ||y|| & 0 \\ 0 & 0\end{array}\right]$

So $AA^T = U\Sigma^2U^T$ . Similarly $A^TA = V\Sigma^2V^T$ where V can be computed similarly.

Exercise: Compute V

So $A = U \Sigma V^T$ is the SVD of A.

**Isomorphism** · December 17th 2009, 06:23 AM

Originally Posted by awaisysf

The 'T' means transposed.

Consider the four non-zero COLUMN vectors in R^2:
x=[x1, x2]; y=[y1, y2]; w=[w1, w2]; z=[z1, z2]

Let xTw=0, yTz=0, A=xyT, B=wzT

Determine:

c) The Range space and Nullspace of A

As seen in the previous post the nullspace of A is span(w). Compute the range space as an exercise

d) The pseudo-inverse de A

Since you know the SVD of A, compute the pseudo inverse the way it is done here.

e) The singular value decomposition (SVD) of A+B

It is an easy exercise to see that $(A+B)(A+B)^T = AA^T + BB^T$ for the given conditions.

Then you can show by a simple manipulation that $A+B = U ( \Sigma + \tilde{\Sigma} ) V^T$ where $\tilde{\Sigma} = \left[ \begin{array}{cc}0 & 0 \\ 0 & ||z||\, ||w||\end{array}\right]$ and the other parameters are the same as those computed in post #5

Thread: norms and vectors

LinkBack

Thread Tools

Display

norms and vectors

Similar Math Help Forum Discussions

norms on R

[SOLVED] Norms in R^m

Norms help

vector norms and matrix norms

Norms

Search Tags