New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Matrix.jordan_cells() fails #10220

Closed
pascalito opened this Issue Dec 9, 2015 · 0 comments

Comments

Projects
None yet
1 participant
@pascalito
Copy link

pascalito commented Dec 9, 2015

I have SymPy 0.7.7.dev (Python 2.7.6-64-bit) and the following matrix:

M = Matrix([
   ...: [1, 0, 0, 1],
   ...: [0, 1, 1, 0],
   ...: [0, 0, 1, 1],
   ...: [0, 0, 0, 1]])

A 4x4 matrix, not very spectacular. However, the following computation fails:

M.jordan_cells()

Here is what my interpreter says:

/usr/local/lib/python2.7/dist-packages/sympy-0.7.7.dev-py2.7.egg/sympy/matrices/matrices.pyc in jordan_cells(self, calc_transformation)
3827 P = MutableMatrix.zeros(n)
3828 for j in range(0, n):
-> 3829 P[:, j] = Pcols_new[j]
3830
3831 return type(self)(P), Jcells

IndexError: list index out of range

I believe that the Jordan normal form can be computed for this matrix. So I guess I fell in a corner case.
The online engine WolframAlpha finds a solution.
Can anyone help or fix?

jordan_cells_failure.txt

jksuom added a commit to jksuom/sympy that referenced this issue Dec 16, 2015

Beware of non-orthogonal Jordan blocks
The matrix
```
M = Matrix([[1, 0, 0, 1],
   	     [0, 1, 1, 0],
   	     [0, 0, 1, 1],
   	     [0, 0, 0, 1]])
```
has a single fourfold eigenvalue 1 and only two eigenvectors
``[1, 0. 0, 0]`` and ``[0, 1, 0, 0]`` considered as column vectors.
(The first two columns of ``M``.) The latter belongs to a Jordan block
of dimension three generated by (the columns of)
```
[0, 1, 0]
[1, 0, 0]
[0, 1, 0]
[0, 0, 1]
```
These vectors form a Jordan chain with the last column as the chain leader.
The others are obtained by repeatedly applying ``M - I`` (where ``I`` is
the identity matrix) so that they are on different "levels". The first one
is in the kernel of ``M - I`` (together with ``[1, 0, 0, 0]``). The middle
column is in the kernel of ``(M - I)**2`` while the last column is annulled
only by ``(M - I)**3``. The first eigenvector is also a chain leader and
spans a block of dimension one.

The Jordan chains belonging to the eigenvalue 1 are found by first
constructing the increasing sequence ``Ns[s]`` of kernels of
``(M - I)**s`` for ``s = 1, 2, 3``. The chain leaders belonging to
``Ns[3]`` are among those that do not belong to ``Ns[2]``. They can be
found by searching vectors that are orthogonal to the subspace ``Ns[2]``.
In this case the orthogonal subspace is one-dimensional, generated by
``[0, 0, 0, 1]``. The corresponding chain is 3-dimensional.

There remains only a single one-dimensional block generated by a vector
of ``Ns[1]`` not belonging to the first-found chain. Such a vector
``[1, 0, 0, 0]`` is again found by orthogonality, but one must be
careful to not demand orthogonality with respect to all chain vectors
found previously. Only the one on the same level, namely ``[0, 1, 0, 0]``,
is to be used. If also the second chain vector ``[1, 0, 1, 0]`` on the
next level is taken into account, no vectors remain to be found.

Fixes sympy#10220

skirpichev added a commit to skirpichev/diofant that referenced this issue Jul 16, 2016

Beware of non-orthogonal Jordan blocks
The matrix
```
M = Matrix([[1, 0, 0, 1],
           [0, 1, 1, 0],
           [0, 0, 1, 1],
           [0, 0, 0, 1]])
```
has a single fourfold eigenvalue 1 and only two eigenvectors
``[1, 0. 0, 0]`` and ``[0, 1, 0, 0]`` considered as column vectors.
(The first two columns of ``M``.) The latter belongs to a Jordan block
of dimension three generated by (the columns of)
```
[0, 1, 0]
[1, 0, 0]
[0, 1, 0]
[0, 0, 1]
```
These vectors form a Jordan chain with the last column as the chain leader.
The others are obtained by repeatedly applying ``M - I`` (where ``I`` is
the identity matrix) so that they are on different "levels". The first one
is in the kernel of ``M - I`` (together with ``[1, 0, 0, 0]``). The middle
column is in the kernel of ``(M - I)**2`` while the last column is annulled
only by ``(M - I)**3``. The first eigenvector is also a chain leader and
spans a block of dimension one.

The Jordan chains belonging to the eigenvalue 1 are found by first
constructing the increasing sequence ``Ns[s]`` of kernels of
``(M - I)**s`` for ``s = 1, 2, 3``. The chain leaders belonging to
``Ns[3]`` are among those that do not belong to ``Ns[2]``. They can be
found by searching vectors that are orthogonal to the subspace ``Ns[2]``.
In this case the orthogonal subspace is one-dimensional, generated by
``[0, 0, 0, 1]``. The corresponding chain is 3-dimensional.

There remains only a single one-dimensional block generated by a vector
of ``Ns[1]`` not belonging to the first-found chain. Such a vector
``[1, 0, 0, 0]`` is again found by orthogonality, but one must be
careful to not demand orthogonality with respect to all chain vectors
found previously. Only the one on the same level, namely ``[0, 1, 0, 0]``,
is to be used. If also the second chain vector ``[1, 0, 1, 0]`` on the
next level is taken into account, no vectors remain to be found.

Fixes sympy/sympy#10220

// edited by skirpichev

Signed-off-by: Sergey B Kirpichev <skirpichev@gmail.com>

skirpichev added a commit to skirpichev/diofant that referenced this issue Jul 17, 2016

Beware of non-orthogonal Jordan blocks
The matrix
```
M = Matrix([[1, 0, 0, 1],
           [0, 1, 1, 0],
           [0, 0, 1, 1],
           [0, 0, 0, 1]])
```
has a single fourfold eigenvalue 1 and only two eigenvectors
``[1, 0. 0, 0]`` and ``[0, 1, 0, 0]`` considered as column vectors.
(The first two columns of ``M``.) The latter belongs to a Jordan block
of dimension three generated by (the columns of)
```
[0, 1, 0]
[1, 0, 0]
[0, 1, 0]
[0, 0, 1]
```
These vectors form a Jordan chain with the last column as the chain leader.
The others are obtained by repeatedly applying ``M - I`` (where ``I`` is
the identity matrix) so that they are on different "levels". The first one
is in the kernel of ``M - I`` (together with ``[1, 0, 0, 0]``). The middle
column is in the kernel of ``(M - I)**2`` while the last column is annulled
only by ``(M - I)**3``. The first eigenvector is also a chain leader and
spans a block of dimension one.

The Jordan chains belonging to the eigenvalue 1 are found by first
constructing the increasing sequence ``Ns[s]`` of kernels of
``(M - I)**s`` for ``s = 1, 2, 3``. The chain leaders belonging to
``Ns[3]`` are among those that do not belong to ``Ns[2]``. They can be
found by searching vectors that are orthogonal to the subspace ``Ns[2]``.
In this case the orthogonal subspace is one-dimensional, generated by
``[0, 0, 0, 1]``. The corresponding chain is 3-dimensional.

There remains only a single one-dimensional block generated by a vector
of ``Ns[1]`` not belonging to the first-found chain. Such a vector
``[1, 0, 0, 0]`` is again found by orthogonality, but one must be
careful to not demand orthogonality with respect to all chain vectors
found previously. Only the one on the same level, namely ``[0, 1, 0, 0]``,
is to be used. If also the second chain vector ``[1, 0, 1, 0]`` on the
next level is taken into account, no vectors remain to be found.

Fixes sympy/sympy#10220

// edited by skirpichev

Signed-off-by: Sergey B Kirpichev <skirpichev@gmail.com>

skirpichev added a commit to skirpichev/diofant that referenced this issue Jul 17, 2016

Beware of non-orthogonal Jordan blocks
The matrix
```
M = Matrix([[1, 0, 0, 1],
           [0, 1, 1, 0],
           [0, 0, 1, 1],
           [0, 0, 0, 1]])
```
has a single fourfold eigenvalue 1 and only two eigenvectors
``[1, 0. 0, 0]`` and ``[0, 1, 0, 0]`` considered as column vectors.
(The first two columns of ``M``.) The latter belongs to a Jordan block
of dimension three generated by (the columns of)
```
[0, 1, 0]
[1, 0, 0]
[0, 1, 0]
[0, 0, 1]
```
These vectors form a Jordan chain with the last column as the chain leader.
The others are obtained by repeatedly applying ``M - I`` (where ``I`` is
the identity matrix) so that they are on different "levels". The first one
is in the kernel of ``M - I`` (together with ``[1, 0, 0, 0]``). The middle
column is in the kernel of ``(M - I)**2`` while the last column is annulled
only by ``(M - I)**3``. The first eigenvector is also a chain leader and
spans a block of dimension one.

The Jordan chains belonging to the eigenvalue 1 are found by first
constructing the increasing sequence ``Ns[s]`` of kernels of
``(M - I)**s`` for ``s = 1, 2, 3``. The chain leaders belonging to
``Ns[3]`` are among those that do not belong to ``Ns[2]``. They can be
found by searching vectors that are orthogonal to the subspace ``Ns[2]``.
In this case the orthogonal subspace is one-dimensional, generated by
``[0, 0, 0, 1]``. The corresponding chain is 3-dimensional.

There remains only a single one-dimensional block generated by a vector
of ``Ns[1]`` not belonging to the first-found chain. Such a vector
``[1, 0, 0, 0]`` is again found by orthogonality, but one must be
careful to not demand orthogonality with respect to all chain vectors
found previously. Only the one on the same level, namely ``[0, 1, 0, 0]``,
is to be used. If also the second chain vector ``[1, 0, 1, 0]`` on the
next level is taken into account, no vectors remain to be found.

Fixes sympy/sympy#10220

// edited by skirpichev

Signed-off-by: Sergey B Kirpichev <skirpichev@gmail.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment