1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Positive semidefinite matrix

  1. May 25, 2012 #1

    [itex] [/itex]

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

    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]

    2. Relevant 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.

    3. 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!

  2. jcsd
  3. May 25, 2012 #2


    User Avatar
    Homework Helper

    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
  4. May 25, 2012 #3

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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]
  5. May 26, 2012 #4
    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
    \\ 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!


  6. May 26, 2012 #5

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook