```-------- Original-Nachricht --------
> Datum: Fri, 23 Nov 2007 04:40:04 +0900
> Von: unbewusst.sein / weltanschauung.com.invalid
> An: ruby-talk / ruby-lang.org
> Betreff: Re: eigenvector discrepency was (Re: [Matrix] eigenvalues, eigenvectors in Ruby ???)

> Axel Etzold <AEtzold / gmx.de> wrote:
>
> > What is the problem that you are actually trying to solve ?
>
> I've two molecules described with a matrix :
> a = Mol.new( [  [ 0, 1, 1, 0 ],
>                 [ 1, 0, 1, 0 ],
>                 [ 1, 1, 0, 1 ],
>                 [ 0, 0, 1, 0 ] ] )
>
> b = Mol.new( [  [ 0, 1, 1, 1 ],
>                 [ 1, 0, 0, 0 ],
>                 [ 1, 0, 0, 1 ],
>                 [ 1, 0, 1, 0 ] ] )
>
> for example the first one in the first row of a says the carbon numbered
> 1 is connected to the carbon number 0.

>
> i know, from construction a and b differs by a permuation p such that :
>
> p * a * p^(-1) = b
>
> only the numbered of carbon atoms is different in that case.
>
> to state that a === b (within a permutation) it is suffciant to have :
>
> eigenvalues of a === eigenvalues of b without respect to the order
>
> however to find p i need the eigenvectors as given by the article :
>
> http://en.wikipedia.org/wiki/Permutation_matrix
>
> in the aboove case:
> p =
> [ [ 0, 0, 1, 0 ],
>   [ 0, 0, 0, 1 ],
>   [ 1, 0, 0, 0 ],
>   [ 0, 1, 0, 0 ] ]
>
> and computing :
>
> p * a * p^( -1 ) =
> [ [ 0, 1, 1, 1 ],
>   [ 1, 0, 0, 0 ],
>   [ 1, 0, 0, 1 ],
>   [ 1, 0, 1, 0 ] ]
>
> gives b
>
> or computing :
>
> p^( -1 ) * b * p =
> [ [ 0, 1, 1, 0 ],
>   [ 1, 0, 1, 0 ],
>   [ 1, 1, 0, 1 ],
>   [ 0, 0, 1, 0 ] ]
>
> i do have a first version of a script using GSL, working as expected.
> however with ExtendedMatrix i'm unable to find p from eigenvectors.
>
> using GSL or ExtendedMatrix i get the same eigenvalues :
> GSL:
> a.eigval = [ 2.170e+00 3.111e-01 -1.000e+00 -1.481e+00 ]
> b.eigval = [ 2.170e+00 -1.481e+00 3.111e-01 -1.000e+00 ]
> ExtendedMatrix
> a.eigval = Vector[-1.0, 2.17008648662603, -1.48119430409202,
> 0.311107817465982]
> b.eigval = Vector[-1.48119430409202, 0.311107817465982, -1.0,
> 2.17008648662603]
>
>
>
> with GSL, if i compare the eigenvectors :
> a.eigvec = [
>    5.227e-01  3.682e-01 -7.071e-01  3.020e-01
>    5.227e-01  3.682e-01  7.071e-01  3.020e-01
>    6.116e-01 -2.536e-01  0.0       -7.494e-01
>    2.818e-01 -8.152e-01  0.0        5.059e-01 ]
> b.eigvec = [
>    6.116e-01  7.494e-01  2.536e-01  0.0
>    2.818e-01 -5.059e-01  8.152e-01  0.0
>    5.227e-01 -3.020e-01 -3.682e-01 -7.071e-01
>    5.227e-01 -3.020e-01 -3.682e-01  7.071e-01 ]
>
> ( i've rounded to 0.0 the values below e-15)
>
> >from column 0 it's easy to see what aa to be permuted
> (all the values are the same but in a different order)
> the first 5.227e-01 in a.eigvec column 0 is found in the third row of
> b.eigvec column 0 then p[0, 2] = 1
> the second 5.227e-01 in a.eigvec column 0 is found in the last row of
> b.eigvec column 0 then p[1, 3] = 1
> the 6.116e-01 (row 2) in a.eigvec column 0 is found in the first row of
> b.eigvec column 0 then p[2, 1] = 1
> the 2.818e-01 (row 3) in a.eigvec column 0 is found in the second row of
> b.eigvec column 0 then p[3, 1] = 1
>
> giving :
>
> [ [ 0, 0, 1, 0 ],
>   [ 0, 0, 0, 1 ],
>   [ 1, 0, 0, 0 ],
>   [ 0, 1, 0, 0 ] ]
>
> unfortunately i don't have any theoretical suggestification of this
> procedure...
>

The permutation matrices are rotation matrices (http://en.wikipedia.org/wiki/Rotation_matrix), if and only if the permutation is even (the number of elements exchanged is even). Then, they can be decomposed into rotations of 45 degrees (i.e. exchanges of coordinates x,y different planes).
http://en.wikipedia.org/wiki/Orthogonal_matrix

With respect to computations of the matrices, both for GSL and extended_matrix, you'll get a matrix composed of columns which are
eigenvectors - thus put the eigenvectors from extended_matrix
together, and see what happens - these span a vector space associated to an eigenvalue.
Every vector from that subspace verifies the eigenvalue equation
for that particular eigenvalue.
However, such a vector would still verify that equation, if you multiplied
every entry by, say, 2.
So, in order to make it a permutation, one must additionally
request that the vectors at hand form an orthonormal basis of the
eigenspace rather than an orthogonal one, thus fixing a constant
factor for all entries in the vector in the example above.

There a two procedures to obtain an orthogonal and orthogonal
basis of a vector space - both bear the name Gram-Schmidt procedure.

The orthonormalization requires additionally that one divides the vector obtained by its norm.

See the English and German Wikipedia entries for that procedure for
examples.

I don't know which algorithm is used in extended_matrix.

There is a rather famous paper by the Hungarian mathematician George
Póìya, which deals with enumerations and symmetries of chemical compounds,
whose English translation appeared as a book:

Combinatorial enumeration of groups, graphs, and chemical compounds,
Springer 1987.

It explains the relationship of permutations and rotations as well as other
symmetries ....

The original is in German: Kombinatorische Anzahlbestimmungen f Gruppen,
Graphen und chemische Verbindungen, Acta Mathematica, 68 (1937), 145-254,
whichever you prefer :)

Best regards,

Axel

--
Ist Ihr Browser Vista-kompatibel? Jetzt die neuesten