Prev: Polynomial used to create Galois field for AES?
Next: Ariel Caticha / The Information Geometry of Space and Time
From: Kaba on 30 Apr 2010 06:06
Kaba wrote:
> Considering an eigenvalue m of A:
> Ax = mx
> =>
> for all x: x^T A x = m x^T x = 0
> =>
> m = 0

This is wrong.. A counter-example is a skew-symmetric matrix

A = [0, a]
[-a, 0]

where a != 0
which has eigenvalues
m_1 = ia
m_2 = -ia
and eigenvectors
q_1 = [1, i]
q_2 = [1, -i]

The problem is in assuming real eigenvectors. Here:
q_1^T q_1 = 1^2 + i^2 = 0
q_2^T q_2 = 1^2 + (-i)^2 = 0
and we can't say anything about m_1 or m_2. Thus the resulting proof is
incorrect too.

Let's generalize to skew-Hermitian matrices. Then it holds that
for all x: x^H A x = 0

Then for eigenvector q and eigenvalue m:
Aq = mq
=>
q^H Aq = m q^H q = 0
=>
m = 0

Here q != 0, by the definition of an eigenvector, and thus q^H q > 0.
But this is wrong too, counter-example being given by:

A = [0, i]
[i, 0]

which is skew-Hermitian and has eigenvalues
m_1 = i
m_2 = -i
and eigenvectors
q_1 = [1, 1]
q_2 = [1, -1]

Where does the logic go wrong?

--
http://kaba.hilvi.org
From: Kaba on 30 Apr 2010 06:23
Robert Israel wrote:
> Kaba <none(a)here.com> writes:
> > > >> Problem:
> > > >> Let A be a skew-symmetric matrix over the reals, i.e. A^T = -A. Show
> > > >> that I + A is invertible.
> > > >>
> > > >> Any hints for a proof?
>
> > How about the iA hint? All I got was that iA is Hermitian.
>
> And what do you know about eigenvalues of Hermitian matrices?

Eigenvalues of Hermitian matrices are real. A Hermitian matrix
diagonalizes, thus:

iA = U D U^H

for some unitary U and real diagonal D. Thus:

A = U (-i D) U^H
=>
A + aI = U (-iD + aI) U^H

for all real a != 0.

Therefore all eigenvalues of A + aI are non-zero. Because the
determinant is the product of eigenvalues, det(A + aI) != 0.
Thus A + aI is invertible. By substituting a = 1, we see that A + I is
invertible.

Thanks.

--
http://kaba.hilvi.org
From: Stephen Montgomery-Smith on 30 Apr 2010 09:10
Kaba wrote:
> Kaba wrote:
>> Considering an eigenvalue m of A:
>> Ax = mx
>> =>
>> for all x: x^T A x = m x^T x = 0
>> =>
>> m = 0
>
> This is wrong.. A counter-example is a skew-symmetric matrix
>
> A = [0, a]
> [-a, 0]
>
> where a != 0
> which has eigenvalues
> m_1 = ia
> m_2 = -ia
> and eigenvectors
> q_1 = [1, i]
> q_2 = [1, -i]
>
> The problem is in assuming real eigenvectors. Here:
> q_1^T q_1 = 1^2 + i^2 = 0
> q_2^T q_2 = 1^2 + (-i)^2 = 0
> and we can't say anything about m_1 or m_2. Thus the resulting proof is
> incorrect too.
>
> Let's generalize to skew-Hermitian matrices. Then it holds that
> for all x: x^H A x = 0
>
> Then for eigenvector q and eigenvalue m:
> Aq = mq
> =>
> q^H Aq = m q^H q = 0
> =>
> m = 0
>
> Here q != 0, by the definition of an eigenvector, and thus q^H q> 0.
> But this is wrong too, counter-example being given by:
>
> A = [0, i]
> [i, 0]
>
> which is skew-Hermitian and has eigenvalues
> m_1 = i
> m_2 = -i
> and eigenvectors
> q_1 = [1, 1]
> q_2 = [1, -1]
>
> Where does the logic go wrong?
>


If A+I is non-invertible, then -1 is an eigenvalue of A. This follows
by definition of eigenvalue. Your argument shows that -1 cannot be an
eigenvalue of A. It also shortens the argument that you created from
Robert's hint.
From: Kaba on 1 May 2010 10:49
Stephen Montgomery-Smith wrote:
> If A+I is non-invertible, then -1 is an eigenvalue of A. This follows
> by definition of eigenvalue. Your argument shows that -1 cannot be an
> eigenvalue of A. It also shortens the argument that you created from
> Robert's hint.

Hmm. But my argument seems to show that _all_ eigenvalues are zero which
can't be the case.

--
http://kaba.hilvi.org
From: Stephen Montgomery-Smith on 1 May 2010 14:22
Kaba wrote:
> Stephen Montgomery-Smith wrote:
>> If A+I is non-invertible, then -1 is an eigenvalue of A. This follows
>> by definition of eigenvalue. Your argument shows that -1 cannot be an
>> eigenvalue of A. It also shortens the argument that you created from
>> Robert's hint.
>
> Hmm. But my argument seems to show that _all_ eigenvalues are zero which
> can't be the case.
>

If the eigenvalue is complex, then the eigenvector is complex as well.
So you cannot conclude that x^T x is non-zero, which is an essential
part of your argument.

You really need to then consider x^* A x, where * represents the
conjugate transpose.
First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: Polynomial used to create Galois field for AES?
Next: Ariel Caticha / The Information Geometry of Space and Time