# Positive semidefinite matrix

1. May 25, 2012

### brian_m.

Hello.



1. The problem statement, all variables and given/known data

Let $x \in \mathbb R^n$ and $t \in \mathbb R$.

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

2. Relevant equations

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

3. The attempt at a solution

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

Bye,
Brian

2. May 25, 2012

### 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

3. May 25, 2012

### Ray Vickson

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

4. May 26, 2012

### brian_m.

Now I have calculated $Y^T A Y$. It is:

$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.$

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

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

Bye,

Brian

5. May 26, 2012

### Ray Vickson

Try again. I get $Q(y,z) = Y^T A Y = t ||y||^2 + 2 <x,y> z + t z^2,$ where $<.,.>$ denotes the inner product and $||\cdot ||$ 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