MATLAB Central Newsreader - Solving x'Px = v

Solving x'Px = v

Benp P — Fri, 12 Dec 2008 00:15:04 -0500

Hi, I need to solve the equation

x'Px = v

where x is an (n by 1) vector of unknowns and P is a (n by n) square matrix (v is a scalar).

Any help would be great!

Thanks,
Ben.

Re: Solving x'Px = v

Roger Stafford — Fri, 12 Dec 2008 00:38:03 -0500

"Benp P" <lightatron@hotmail.com> wrote in message <ghsae8$nlk$1@fred.mathworks.com>...
> Hi, I need to solve the equation
>
> x'Px = v
>
> where x is an (n by 1) vector of unknowns and P is a (n by n) square matrix (v is a scalar).
>
> Any help would be great!
>
> Thanks,
> Ben.

If one were to let P = [1 0;0 1] this would yield the equation

x^2 + y^2 = v

for the unknown vector [x;y]. In other words you would be giving us the equation of a circle and asking us to find its solution. That doesn't make much sense to me. There are infinitely many solutions, and the same would be true in general for your quadratic equation x'*P*x = v. There are n unknowns and only one equation.

Roger Stafford

Re: Solving x'Px = v

Benp P — Fri, 12 Dec 2008 00:47:02 -0500

Thanks for your reply.
There are other constraints on x for solving explicitly, though I omitted them as I am after an algebraic expression for x (if it exists) in terms of P and v.

Thanks,
Ben.

Re: Solving x'Px = v

Benp P — Fri, 12 Dec 2008 00:50:04 -0500

Thanks for your reply.
There are other constraints on x, though I omitted them as I am after an algebraic expression for x (if it exists) in terms of P and v.

Thanks again,
Ben.

Re: Solving x'Px = v

John D'Errico — Fri, 12 Dec 2008 01:16:02 -0500

"Benp P" <lightatron@hotmail.com> wrote in message <ghscfs$kp7$1@fred.mathworks.com>...
> Thanks for your reply.
> There are other constraints on x, though I omitted them as I am after an algebraic expression for x (if it exists) in terms of P and v.
>
> Thanks again,
> Ben.

This IS the expression. Depending upon the
characteristics of P, this is the equation of a
circle/sphere, or perhaps an ellipsoid, or
perhaps some other conic form, all in
n-dimensions.

Sorry, but there is no simple expression for
you here.

John

Re: Solving x'Px = v

swgillan — Fri, 12 Dec 2008 07:26:47 -0500

On Dec 11, 4:15=A0pm, "Benp P" <lightat...@hotmail.com> wrote:
> Hi, I need to solve the equation
>
> x'Px =3D v
>
> where x is an (n by 1) vector of unknowns and P is a (n by n) square matr=
ix (v is a scalar).
>
> Any help would be great!
>
> Thanks,
> Ben.

Not sure of this would help, but can you perform a cholesky
factorization on P? P =3D LL' where L is a lower triangular.

x'Px =3D v
x'LL'x =3D v
let L'x =3D y
y'y =3D v

if you can find y, you can just do simple back substition to get x.

Not sure if that helps or not.

Re: Solving x'Px = v

John D'Errico — Fri, 12 Dec 2008 10:00:05 -0500

swgillan <swgillan@gmail.com> wrote in message <51a9e61a-47f4-4b75-8c09-0538d1323b82@x16g2000prn.googlegroups.com>...
> On Dec 11, 4:15=A0pm, "Benp P" <lightat...@hotmail.com> wrote:
> > Hi, I need to solve the equation
> >
> > x'Px =3D v
> >
> > where x is an (n by 1) vector of unknowns and P is a (n by n) square matr=
> ix (v is a scalar).
> >
> > Any help would be great!
> >
> > Thanks,
> > Ben.
>
> Not sure of this would help, but can you perform a cholesky
> factorization on P? P =3D LL' where L is a lower triangular.
>
> x'Px =3D v
> x'LL'x =3D v
> let L'x =3D y
> y'y =3D v
>
> if you can find y, you can just do simple back substition to get x.
>
> Not sure if that helps or not.

Its an idea, although the OP has never stated that
P is positive definite, a HUGEly important factor
in the existence of a Cholesky factor.

Essentially, IF P is symmetric and positive definite,
then X'*P*X = v is the equation of a hyper-ellipsoid.
All the Cholesky factor does is to transform the
ellipsoid into a hyper-sphere, still in n dimensions.
Having then turned the problem into Y'*Y = v,
you still do not have a solution for y. Remember,
the OP has asked for a way to recover the unknown.

All that we know is that y lies on a hyper-sphere
of known radius.

If P is a general matrix, this will fail, although one
might choose another form to factorize P. Perhaps
an LDL' or UDU' form might be chosen. Note that
D need not always be a diagonal matrix in these
forms.

John