Is the Matrix Positive Semidefinite Given the Norm Condition?

[brian_m.]

Hello.

[itex] [/itex]

Homework Statement

Let [itex]x \in \mathbb R^n[/itex] and [itex]t \in \mathbb R[/itex].


Prove the following equivalence:
[itex]\left \| x \right \|_2 \leq t \ \ \Leftrightarrow \ \ \begin{pmatrix} t \cdot I_n & x \\ x^T & t \end{pmatrix} \text{is positive semidefinite }[/itex]

Homework Equations

[itex]\left \| x \right \|_2 = \sqrt{x_1^2+ ... + x_n^2}[/itex] is the euclidean norm and [itex]I_n [/itex] the identity matrix of dimension n.

The Attempt at a Solution

I know that a matrix is positive semidefinite if and only if all eigenvalues of the matrix are [itex]\geq 0[/itex].
My problem is to calculate the eigenvalues of the given matrix.

Thank your for your help in advance!

Bye,
Brian

 

[lanedance]

yeah so I would probably start by trying to find the characteristic equation of the matrix

as they're only 2 non-zero rows in the first column, hopefully it shoudl simplify a fair bit

 

[Ray Vickson]

Hello.

[itex] [/itex]

Homework Statement

Let [itex]x \in \mathbb R^n[/itex] and [itex]t \in \mathbb R[/itex].


Prove the following equivalence:
[itex]\left \| x \right \|_2 \leq t \ \ \Leftrightarrow \ \ \begin{pmatrix} t \cdot I_n & x \\ x^T & t \end{pmatrix} \text{is positive semidefinite }[/itex]

Homework Equations

[itex]\left \| x \right \|_2 = \sqrt{x_1^2+ ... + x_n^2}[/itex] is the euclidean norm and [itex]I_n [/itex] the identity matrix of dimension n.

The Attempt at a Solution

I know that a matrix is positive semidefinite if and only if all eigenvalues of the matrix are [itex]\geq 0[/itex].
My problem is to calculate the eigenvalues of the given matrix.

Thank your for your help in advance!

Bye,
Brian

It is much easier if you forget about eigenvalues and look directly at the _defintion_ of psd (positive semi-definite). Your matrix [tex] A = \begin{pmatrix} t \cdot I_n & x \\ x^T & t \end{pmatrix}[/tex] is psd if, for all [itex] Y \in \mathbb R^{n+1}[/itex] we have
[itex] Y^T A Y \geq 0.[/itex] Letting
[tex] Y = \begin{pmatrix} y \\ z \end{pmatrix}, \; y \in \mathbb{R}^n, \; z \in \mathbb{R},[/tex] the quadratic form [itex]Q(y,z) = Y^T A Y[/itex] is easily computed. For alll [itex] y \in \mathbb{R}^n[/itex] we need [itex] Q \geq 0, [/itex] so considered as an optimization problem in [itex] z[/itex] we can derive a simple necessary and sufficient condition involving [itex] ||x|| \text{ and } t.[/itex]

 

[brian_m.]

Thanks for your help.

Now I have calculated [itex]Y^T A Y[/itex]. It is:

[itex]Y^T A Y = \begin{pmatrix}
y & z \end{pmatrix} \begin{pmatrix} t \cdot I_n & x \\ x^T & t \end{pmatrix} \begin{pmatrix}
y\\z \end{pmatrix} = \begin{pmatrix}
y_1t+zx_1 & \cdots & y_nt+zx_n & y_1x_1+...+y_nx_n+zt
\end{pmatrix}\begin{pmatrix}
y_1\\\vdots
\\ y_n
\\ z
\end{pmatrix}= \\
= \sum_{i=1}^n y_i^2 t + 2z \sum_{i=1}^n y_i x_i. [/itex]

So I have to find out for which [itex]z[/itex] the inequality [itex]t \cdot \sum_{i=1}^n y_i^2 + 2z \cdot \sum_{i=1}^n y_i x_i \geq 0[/itex] holds?

I don't know how to find out the solution of the inequality. Please can you help me again?

Thank you in adavance!

Bye,

Brian

 

[Ray Vickson]

Thanks for your help.

Now I have calculated [itex]Y^T A Y[/itex]. It is:

[itex]Y^T A Y = \begin{pmatrix}
y & z \end{pmatrix} \begin{pmatrix} t \cdot I_n & x \\ x^T & t \end{pmatrix} \begin{pmatrix}
y\\z \end{pmatrix} = \begin{pmatrix}
y_1t+zx_1 & \cdots & y_nt+zx_n & y_1x_1+...+y_nx_n+zt
\end{pmatrix}\begin{pmatrix}
y_1\\\vdots
\\ y_n
\\ z
\end{pmatrix}= \\
= \sum_{i=1}^n y_i^2 t + 2z \sum_{i=1}^n y_i x_i. [/itex]

So I have to find out for which [itex]z[/itex] the inequality [itex]t \cdot \sum_{i=1}^n y_i^2 + 2z \cdot \sum_{i=1}^n y_i x_i \geq 0[/itex] holds?

I don't know how to find out the solution of the inequality. Please can you help me again?

Thank you in adavance!

Bye,

Brian

Try again. I get [itex] Q(y,z) = Y^T A Y = t ||y||^2 + 2 <x,y> z + t z^2,[/itex] where [itex]<.,.>[/itex] denotes the inner product and [itex] ||\cdot ||[/itex] the usual norm. For any y, Q(y,z) must be ≥ 0, which means that as a function of z it cannot have two distinct roots.

RGV