A Theorem about eigenvalues
Peter B
Let A be a diagonal p-dim matrix with a_1 >= a_2 >=…>= a_p >=0 on the
diagonal. For an arbitrary column vector v, the matrix (A + v*t(v))
has the eigenvalues b_1>=b_2>=…>=b_p>=0 such that b_i >= a_i for all
i=1,…,p.
Note: t(v) is a transpose of v, that is, a row vector (so, v*t(v) is a
matrix).
I can prove it only in some special cases, but not in general. Please
let me know, if you have seen anything similar, or know how to prove
it.
Jannick Asmus
Proof by induction on p: For the induction step decompose A + v.t(v) =
t(U).U where U is built by (1,p-1) blocks, i.e. U=((a,t(x)),(0,U')) with
a scalar a, x a (p-1)-vector and U' a (p-1(x(p-1)-matrix.
Hope that this is understandable - even this is just ASCII. ;)
--
Best wishes,
J.
Peter B
wrote:
Thanks, Jannick, for the hint, but I need more help. Your notation is
clear.
I know how to show b_i >= a_i for i=1 and i=p, so the first step for
p=2 is easy.
But I could not do the induction step. It seems that adding one
dimension may change all eigenvalues and eigenvectors, and I was not
able to establish a relationship between eigenvalues of t(U).U and
t(U’).U’, which I’m assuming would be needed here.
Best wishes,
Peter
Jannick Asmus
> On Sep 20, 1:41 pm, Jannick Asmus <jannick.newsREMOVE...@web.de>
> wrote:
>> On 20.09.2008 18:28, Peter B wrote:
>>
>>> I'm looking for a proof of the following Theorem
>>> diagonal. For an arbitrary column vector v, the matrix (A + v*t(v))
>>> i=1,...,p.
>>> Note: t(v) is a transpose of v, that is, a row vector (so, v*t(v) is a
>>> matrix).
>>> I can prove it only in some special cases, but not in general. Please
>>> let me know, if you have seen anything similar, or know how to prove
>>> it.
>> Proof by induction on p: For the induction step decompose A + v.t(v) =
>> t(U).U where U is built by (1,p-1) blocks, i.e. U=((a,t(x)),(0,U')) with
>> a scalar a, x a (p-1)-vector and U' a (p-1(x(p-1)-matrix.
>>
>> Hope that this is understandable - even this is just ASCII. ;)
>>
>> --
>> Best wishes,
>> J.
>
> Thanks, Jannick, for the hint, but I need more help. Your notation is
> clear.
>
> I know how to show b_i >= a_i for i=1 and i=p, so the first step for
> p=2 is easy.
>
> But I could not do the induction step. It seems that adding one
> dimension may change all eigenvalues and eigenvectors, and I was not
> able to establish a relationship between eigenvalues of t(U).U and
> t(U').U', which I'm assuming would be needed here.
Does det(U)^2 = a^2 det(U')^2 help you?
> Best wishes,
>
> Peter
--
Best wishes,
J.
Peter B
This is a general relationship between the products of eigenvalues,
but I think I need something more subtle.
I understand you think it can be done by induction on p, but you do
not have the actual proof. Correct?
karl
> I’m looking for a proof of the following Theorem
>
> Let A be a diagonal p-dim matrix with a_1 >= a_2 >=…>= a_p >=0 on the
> diagonal. For an arbitrary column vector v, the matrix (A + v*t(v))
> has the eigenvalues b_1>=b_2>=…>=b_p>=0 such that b_i >= a_i for all
> i=1,…,p.
>
> Note: t(v) is a transpose of v, that is, a row vector (so, v*t(v) is a
> matrix).
>
There is a theorem in linear algebra about the simultaneous
diagonalization of two quadratic forms, see for example:
home.iitk.ac.in/~rksr/html/00LinearAlgebraandAppliedMatrixTheory.htm -
44k -
That should do the trick.
Ciao
Karl
Peter B
I understand that for the simultaneous diagonalization, the matrices
need to commute, and these matrices do not seem to commute. Correct?
karl
Did you try to find the theorem. No, correct?
Ray Vickson
This is, basically, the interlocking-eigenvalues lemma. The book
"Iterative Solution Methods"
By Owe Axelsson, Google books, http://books.google.ca/books?id=hNpJg_pUsOwC&pg=RA1-PA18&lpg=RA1-PA18
&dq=interlocking+eigenvalues&source=web&ots=8K9Za6fW-
k&sig=bXEcxNhpCtbwZdLPReTETtGcJUI&hl=en
&sa=X&oi=book_result&resnum=5&ct=result (long URL line-wrapped) has
the following exercise on page 118): Let A be symmetric of order n
with n eigenvalues r1 <= r2 <= ... <= rn, and let v be any vector in
R^n. The eigenvalues s1 <= s2 <= ... <= sn of the matrix B = A + v *
t(v) satisfy r1 <= s1 <= r2 <= s2 <= ... <= rn <= sn (interlocking).
Axelsson gives a reference to Loewner, 1934.
The result is used a lot in optimization theory, especially when
developing quasi-Newton methods for nonlinear optimization, so any
good optimization book will have a proof. For example, page 276 of
Luenberger "Linear and Nonlinear Programming" (Google books
http://books.google.ca/books?id=QY9BjisUT1gC&pg=PA277&lpg=PA277
&dq=interlocking
+eigenvalues&source=web&ots=Iv0nSuzQ17&sig=kUF7FYMa8v_mD_pifzpzd_x_t0o
&hl=en&sa=X&oi=book_result&resnum=1&ct=result#PPA276,M1 ) has a proof.
While some pages are omitted from the free, on-line version, the ones
you need are included.
R.G. Vickson
Ray Vickson
> On Sep 20, 9:28 am, Peter B <piot...@gmail.com> wrote:
>
> > I’m looking for a proof of the following Theorem
>
> > Let A be a diagonal p-dim matrix with a_1 >= a_2 >=…>= a_p >=0 on the
> > diagonal. For an arbitrary column vector v, the matrix (A + v*t(v))
> > has the eigenvalues b_1>=b_2>=…>=b_p>=0 such that b_i >= a_i for all
> > i=1,…,p.
>
> > Note: t(v) is a transpose of v, that is, a row vector (so, v*t(v) is a
> > matrix).
>
> > I can prove it only in some special cases, but not in general. Please
> > let me know, if you have seen anything similar, or know how to prove
> > it.
>
> This is, basically, the interlocking-eigenvalues lemma. The book
> "Iterative Solution Methods"
> &dq=interlocking+eigenvalues&source=web&ots=8K9Za6fW-
> k&sig=bXEcxNhpCtbwZdLPReTETtGcJUI&hl=en
> &sa=X&oi=book_result&resnum=5&ct=result (long URL line-wrapped) has
> the following exercise on page 118): Let A be symmetric of order n
> with n eigenvalues r1 <= r2 <= ... <= rn, and let v be any vector in
> R^n. The eigenvalues s1 <= s2 <= ... <= sn of the matrix B = A + v *
> t(v) satisfy r1 <= s1 <= r2 <= s2 <= ... <= rn <= sn (interlocking).
> Axelsson gives a reference to Loewner, 1934.
>
> The result is used a lot in optimization theory, especially when
> developing quasi-Newton methods for nonlinear optimization, so any
> good optimization book will have a proof. For example, page 276 of
> &dq=interlocking
> +eigenvalues&source=web&ots=Iv0nSuzQ17&sig=kUF7FYMa8v_mD_pifzpzd_x_t0o
> &hl=en&sa=X&oi=book_result&resnum=1&ct=result#PPA276,M1 ) has a proof.
Sorry, no. He does not have a proof, only a literature citation.
However, the Axelsson book cited above gives a hint for how to prove
the result. It suggests using the Courant-Fisher Theorem. A Google
search on this produces a number of citations, and one dsec.pku.edu.cn/
~tieli/notes/num_meth/lect4.pdf has a proof. However, I could not get
the pdf version to load and had to go with the somewhat imperfect html
version in http://209.85.173.104/search?q=cache:HXQOn5PU28QJ:dsec.pku.edu.cn/~tieli/notes/num_meth/lect4.pdf
+courant-Fisher+theorem&hl=en&ct=clnk&cd=34&gl=ca&client=firefox-a
R.G. Vickson
Peter B
> +courant-Fisher+theorem&hl=en&ct=clnk&cd=34&gl=ca&client=firefox-a
>
> R.G. Vickson
>
> > While some pages are omitted from the free, on-line version, the ones
> > you need are included.
>
> > R.G. Vickson
>
>
Thanks, R.G. Vickson, this is very helpful. The Courant-Fisher Theorem
is well known, but I still could not find the proof for the
interlocking eigenvalues lemma. The hint in "Iterative Solution
Methods" By Owe Axelsson was not sufficient for me so far.
Loewner (1934) might be difficult to find, but at least I can quote
the interlocking eigenvalues lemma from the sources you suggested.
Jannick Asmus
Sorry for the late reply. I was off-line during the weekend.
Hmm, I thought the proof would go through like this with my hints. My
fault. Sorry about this.
But as Ray has already pointed out the claim is a trivial implication of
Courant-Fisher theorem of the following form:
Let beta be a bilinear form on a n-dimensional euclidean vector space.
Given the eigen values of beta in decreasing order a_n >= ... a_1, then
a_k is the minimum of norm(Q restricted to U) for all subspaces U of
dimension at least k. Here Q denotes the quadratic form induced by beta.
NB: I abused the notion norm here. I think this is ok.
In case there is still a proof needed, here it is - and I am sure it
works. ;)
Let B=A+v.t(v), then given some subspace U we have for the induced
quadratic forms
norm(Q_A restricted to U) <= norm(Q_B restricted to U)
since v.t(v) is semi-positive definite. For k=1,...,n, let U* be a
subspace with dim(U*)>=k and b_k = norm(Q_B restricted to U*), by
Courant-Fisher. Then
a_k <= norm(Q_A restricted to U*) <= norm(Q_B restricted to U*) = b_k,
where the first inequality is implied by Courant-Fisher, again.
--
Best wishes,
J.
Peter B
Yes, the proof works. Thank you very much.
Jannick Asmus
> On Sep 21, 7:15 pm, Jannick Asmus <jannick.newsREMOVE...@web.de>
>> But as Ray has already pointed out the claim is a trivial implication of
>> Courant-Fisher theorem of the following form:
>>
>> Let beta be a bilinear form on a n-dimensional euclidean vector space.
>> Given the eigen values of beta in decreasing order a_n >= ... a_1, then
>> a_k is the minimum of norm(Q restricted to U) for all subspaces U of
>> dimension at least k. Here Q denotes the quadratic form induced by beta.
>>
>> NB: I abused the notion norm here. I think this is ok.
>>
>> In case there is still a proof needed, here it is - and I am sure it
>> works. ;)
>>
>> Let B=A+v.t(v), then given some subspace U we have for the induced
>> quadratic forms
>>
>> norm(Q_A restricted to U) <= norm(Q_B restricted to U)
>>
>> since v.t(v) is semi-positive definite. For k=1,...,n, let U* be a
>> subspace with dim(U*)>=k and b_k = norm(Q_B restricted to U*), by
>> Courant-Fisher. Then
>>
>> a_k <= norm(Q_A restricted to U*) <= norm(Q_B restricted to U*) = b_k,
>>
>> where the first inequality is implied by Courant-Fisher, again.
>>
>> --
>> Best wishes,
>> J.
>
> Yes, the proof works. Thank you very much.
Good to hear.
BTW The proof shows that the claim generalizes to the assumption A <= B
with A,B symmetric or - over the complex numbers - hermititan.
--
Best wishes,
J.