Calculate symplectic bases for matrices over fields and the integers.#

This module finds a symplectic basis for an anti-symmetric, alternating matrix M defined over a field or the integers.

Anti-symmetric means that \(M = -M^t\), where \(M^t\) denotes the transpose of \(M\). Alternating means that the diagonal of \(M\) is identically zero.

A symplectic basis is a basis of the form \(e_1, \ldots, e_j, f_1, \ldots, f_j, z_1, \ldots, z_k\) such that

  • \(z_i M v^t\) = 0 for all vectors \(v\);

  • \(e_i M {e_j}^t = 0\) for all \(i, j\);

  • \(f_i M {f_j}^t = 0\) for all \(i, j\);

  • \(e_i M {f_j}^t = 0\) for all \(i\) not equal \(j\);

and such that the non-zero terms

  • \(e_i M {f_i}^t\) are “as nice as possible”: 1 over fields, or integers satisfying divisibility properties otherwise.

REFERENCES:

Bourbaki gives a nice proof that can be made constructive but is not efficient (see Section 5, Number 1, Theorem 1, page 79):

Bourbaki, N. Elements of Mathematics, Algebra III, Springer Verlag 2007.

Kuperberg gives a more efficient and constructive exposition (see Theorem 18).

Kuperberg, Greg. Kasteleyn Cokernels. Electr. J. Comb. 9(1), 2002.

Todo

The routine over the integers applies over general principal ideal domains.

Warning

This code is not a good candidate for conversion to Cython. The majority of the execution time is spent adding multiples of columns and rows, which is already fast. It would be better to devise a better algorithm, perhaps modular or based on a fast smith_form implementation.

AUTHOR:

  • Nick Alexander: initial implementation

  • David Loeffler (2008-12-08): changed conventions for consistency with smith_form

sage.matrix.symplectic_basis.symplectic_basis_over_ZZ(M)#

Find a symplectic basis for an anti-symmetric, alternating matrix M defined over the integers.

Returns a pair (F, C) such that the rows of C form a symplectic basis for M and F = C * M * C.transpose().

Anti-symmetric means that \(M = -M^t\). Alternating means that the diagonal of \(M\) is identically zero.

A symplectic basis is a basis of the form \(e_1, \ldots, e_j, f_1, \ldots, f_j, z_1, \ldots, z_k\) such that

  • \(z_i M v^t\) = 0 for all vectors \(v\);

  • \(e_i M {e_j}^t = 0\) for all \(i, j\);

  • \(f_i M {f_j}^t = 0\) for all \(i, j\);

  • \(e_i M {f_i}^t = d_i\) for all \(i\), where d_i are positive integers such that \(d_{i} | d_{i+1}\) for all \(i\);

  • \(e_i M {f_j}^t = 0\) for all \(i\) not equal \(j\).

The ordering for the factors \(d_{i} | d_{i+1}\) and for the placement of zeroes was chosen to agree with the output of smith_form.

See the examples for a pictorial description of such a basis.

EXAMPLES:

sage: from sage.matrix.symplectic_basis import symplectic_basis_over_ZZ

An example which does not have full rank:

sage: E = matrix(ZZ, 4, 4, [0, 16, 0, 2, -16, 0, 0, -4, 0, 0, 0, 0, -2, 4, 0, 0]); E
[  0  16   0   2]
[-16   0   0  -4]
[  0   0   0   0]
[ -2   4   0   0]
sage: F, C = symplectic_basis_over_ZZ(E)
sage: F
[ 0  2  0  0]
[-2  0  0  0]
[ 0  0  0  0]
[ 0  0  0  0]
sage: C * E * C.transpose() == F
True

A larger example:

sage: E = matrix(ZZ, 8, 8, [0, 25, 0, 0, -37, -3, 2, -5, -25, 0, 1, -5, -54, -3, 3, 3, 0, -1, 0, 7, 0, -4, -20, 0, 0, 5, -7, 0, 0, 14, 0, -3, 37, 54, 0, 0, 0, 2, 3, -12, 3, 3, 4, -14, -2, 0, -3, 2, -2, -3, 20, 0, -3, 3, 0, -2, 5, -3, 0, 3, 12, -2, 2, 0]); E
[  0  25   0   0 -37  -3   2  -5]
[-25   0   1  -5 -54  -3   3   3]
[  0  -1   0   7   0  -4 -20   0]
[  0   5  -7   0   0  14   0  -3]
[ 37  54   0   0   0   2   3 -12]
[  3   3   4 -14  -2   0  -3   2]
[ -2  -3  20   0  -3   3   0  -2]
[  5  -3   0   3  12  -2   2   0]
sage: F, C = symplectic_basis_over_ZZ(E)
sage: F
[     0      0      0      0      1      0      0      0]
[     0      0      0      0      0      1      0      0]
[     0      0      0      0      0      0      1      0]
[     0      0      0      0      0      0      0  20191]
[    -1      0      0      0      0      0      0      0]
[     0     -1      0      0      0      0      0      0]
[     0      0     -1      0      0      0      0      0]
[     0      0      0 -20191      0      0      0      0]
sage: F == C * E * C.transpose()
True
sage: E.smith_form()[0]
[    1     0     0     0     0     0     0     0]
[    0     1     0     0     0     0     0     0]
[    0     0     1     0     0     0     0     0]
[    0     0     0     1     0     0     0     0]
[    0     0     0     0     1     0     0     0]
[    0     0     0     0     0     1     0     0]
[    0     0     0     0     0     0 20191     0]
[    0     0     0     0     0     0     0 20191]

An odd dimensional example:

sage: E = matrix(ZZ, 5, 5, [0, 14, 0, -8, -2, -14, 0, -3, -11, 4, 0, 3, 0, 0, 0, 8, 11, 0, 0, 8, 2, -4, 0, -8, 0]); E
[  0  14   0  -8  -2]
[-14   0  -3 -11   4]
[  0   3   0   0   0]
[  8  11   0   0   8]
[  2  -4   0  -8   0]
sage: F, C = symplectic_basis_over_ZZ(E)
sage: F
[ 0  0  1  0  0]
[ 0  0  0  2  0]
[-1  0  0  0  0]
[ 0 -2  0  0  0]
[ 0  0  0  0  0]
sage: F == C * E * C.transpose()
True
sage: E.smith_form()[0]
[1 0 0 0 0]
[0 1 0 0 0]
[0 0 2 0 0]
[0 0 0 2 0]
[0 0 0 0 0]

sage: F.parent()
Full MatrixSpace of 5 by 5 dense matrices over Integer Ring
sage: C.parent()
Full MatrixSpace of 5 by 5 dense matrices over Integer Ring
sage.matrix.symplectic_basis.symplectic_basis_over_field(M)#

Find a symplectic basis for an anti-symmetric, alternating matrix M defined over a field.

Returns a pair (F, C) such that the rows of C form a symplectic basis for M and F = C * M * C.transpose().

Anti-symmetric means that \(M = -M^t\). Alternating means that the diagonal of \(M\) is identically zero.

A symplectic basis is a basis of the form \(e_1, \ldots, e_j, f_1, \ldots f_j, z_1, \ldots, z_k\) such that

  • \(z_i M v^t\) = 0 for all vectors \(v\);

  • \(e_i M {e_j}^t = 0\) for all \(i, j\);

  • \(f_i M {f_j}^t = 0\) for all \(i, j\);

  • \(e_i M {f_i}^t = 1\) for all \(i\);

  • \(e_i M {f_j}^t = 0\) for all \(i\) not equal \(j\).

See the examples for a pictorial description of such a basis.

EXAMPLES:

sage: from sage.matrix.symplectic_basis import symplectic_basis_over_field

A full rank exact example:

sage: E = matrix(QQ, 8, 8, [0, -1/2, -2, 1/2, 2, 0, -2, 1, 1/2, 0, -1, -3, 0, 2, 5/2, -3, 2, 1, 0, 3/2, -1, 0, -1, -2, -1/2, 3, -3/2, 0, 1, 3/2, -1/2, -1/2, -2, 0, 1, -1, 0, 0, 1, -1, 0, -2, 0, -3/2, 0, 0, 1/2, -2, 2, -5/2, 1, 1/2, -1, -1/2, 0, -1, -1, 3, 2, 1/2, 1, 2, 1, 0]); E
[   0 -1/2   -2  1/2    2    0   -2    1]
[ 1/2    0   -1   -3    0    2  5/2   -3]
[   2    1    0  3/2   -1    0   -1   -2]
[-1/2    3 -3/2    0    1  3/2 -1/2 -1/2]
[  -2    0    1   -1    0    0    1   -1]
[   0   -2    0 -3/2    0    0  1/2   -2]
[   2 -5/2    1  1/2   -1 -1/2    0   -1]
[  -1    3    2  1/2    1    2    1    0]
sage: F, C = symplectic_basis_over_field(E); F
[ 0  0  0  0  1  0  0  0]
[ 0  0  0  0  0  1  0  0]
[ 0  0  0  0  0  0  1  0]
[ 0  0  0  0  0  0  0  1]
[-1  0  0  0  0  0  0  0]
[ 0 -1  0  0  0  0  0  0]
[ 0  0 -1  0  0  0  0  0]
[ 0  0  0 -1  0  0  0  0]
sage: F == C * E * C.transpose()
True

An example over a finite field:

sage: E = matrix(GF(7), 8, 8, [0, -1/2, -2, 1/2, 2, 0, -2, 1, 1/2, 0, -1, -3, 0, 2, 5/2, -3, 2, 1, 0, 3/2, -1, 0, -1, -2, -1/2, 3, -3/2, 0, 1, 3/2, -1/2, -1/2, -2, 0, 1, -1, 0, 0, 1, -1, 0, -2, 0, -3/2, 0, 0, 1/2, -2, 2, -5/2, 1, 1/2, -1, -1/2, 0, -1, -1, 3, 2, 1/2, 1, 2, 1, 0]); E
[0 3 5 4 2 0 5 1]
[4 0 6 4 0 2 6 4]
[2 1 0 5 6 0 6 5]
[3 3 2 0 1 5 3 3]
[5 0 1 6 0 0 1 6]
[0 5 0 2 0 0 4 5]
[2 1 1 4 6 3 0 6]
[6 3 2 4 1 2 1 0]
sage: F, C = symplectic_basis_over_field(E); F
[0 0 0 0 1 0 0 0]
[0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 1 0]
[0 0 0 0 0 0 0 1]
[6 0 0 0 0 0 0 0]
[0 6 0 0 0 0 0 0]
[0 0 6 0 0 0 0 0]
[0 0 0 6 0 0 0 0]
sage: F == C * E * C.transpose()
True

The tricky case of characteristic 2:

sage: E = matrix(GF(2), 8, 8, [0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0]); E
[0 0 1 1 0 1 0 1]
[0 0 0 0 0 0 0 0]
[1 0 0 0 0 0 1 1]
[1 0 0 0 0 0 0 1]
[0 0 0 0 0 1 1 0]
[1 0 0 0 1 0 1 1]
[0 0 1 0 1 1 0 0]
[1 0 1 1 0 1 0 0]
sage: F, C = symplectic_basis_over_field(E); F
[0 0 0 1 0 0 0 0]
[0 0 0 0 1 0 0 0]
[0 0 0 0 0 1 0 0]
[1 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
sage: F == C * E * C.transpose()
True

An inexact example:

sage: E = matrix(RR, 8, 8, [0.000000000000000, 0.420674846479344, -0.839702420666807, 0.658715385244413, 1.69467394825853, -1.14718543053828, 1.03076138152950, -0.227739521708484, -0.420674846479344, 0.000000000000000, 0.514381455379082, 0.282194064028260, -1.38977093018412, 0.278305070958958, -0.0781320488361574, -0.496003664217833, 0.839702420666807, -0.514381455379082, 0.000000000000000, -0.00618222322875384, -0.318386939149028, -0.0840205427053993, 1.28202592892333, -0.512563654267693, -0.658715385244413, -0.282194064028260, 0.00618222322875384, 0.000000000000000, 0.852525732369211, -0.356957405431611, -0.699960114607661, 0.0260496330859998, -1.69467394825853, 1.38977093018412, 0.318386939149028, -0.852525732369211, 0.000000000000000, -0.836072521423577, 0.450137632758469, -0.696145287292091, 1.14718543053828, -0.278305070958958, 0.0840205427053993, 0.356957405431611, 0.836072521423577, 0.000000000000000, 0.214878541347751, -1.20221688928379, -1.03076138152950, 0.0781320488361574, -1.28202592892333, 0.699960114607661, -0.450137632758469, -0.214878541347751, 0.000000000000000, 0.785074452163036, 0.227739521708484, 0.496003664217833, 0.512563654267693, -0.0260496330859998, 0.696145287292091, 1.20221688928379, -0.785074452163036, 0.000000000000000]); E
[   0.000000000000000    0.420674846479344   -0.839702420666807    0.658715385244413     1.69467394825853    -1.14718543053828     1.03076138152950   -0.227739521708484]
[  -0.420674846479344    0.000000000000000    0.514381455379082    0.282194064028260    -1.38977093018412    0.278305070958958  -0.0781320488361574   -0.496003664217833]
[   0.839702420666807   -0.514381455379082    0.000000000000000 -0.00618222322875384   -0.318386939149028  -0.0840205427053993     1.28202592892333   -0.512563654267693]
[  -0.658715385244413   -0.282194064028260  0.00618222322875384    0.000000000000000    0.852525732369211   -0.356957405431611   -0.699960114607661   0.0260496330859998]
[   -1.69467394825853     1.38977093018412    0.318386939149028   -0.852525732369211    0.000000000000000   -0.836072521423577    0.450137632758469   -0.696145287292091]
[    1.14718543053828   -0.278305070958958   0.0840205427053993    0.356957405431611    0.836072521423577    0.000000000000000    0.214878541347751    -1.20221688928379]
[   -1.03076138152950   0.0781320488361574    -1.28202592892333    0.699960114607661   -0.450137632758469   -0.214878541347751    0.000000000000000    0.785074452163036]
[   0.227739521708484    0.496003664217833    0.512563654267693  -0.0260496330859998    0.696145287292091     1.20221688928379   -0.785074452163036    0.000000000000000]
sage: F, C = symplectic_basis_over_field(E); F # random
[    0.000000000000000     0.000000000000000  2.22044604925031e-16 -2.22044604925031e-16      1.00000000000000     0.000000000000000     0.000000000000000 -3.33066907387547e-16]
[    0.000000000000000  8.14814392305203e-17 -1.66533453693773e-16 -1.11022302462516e-16     0.000000000000000      1.00000000000000 -1.11022302462516e-16     0.000000000000000]
[-5.27829526256056e-16 -2.40004077757759e-16  1.28373418199470e-16 -1.11022302462516e-16     0.000000000000000 -3.15483812822081e-16      1.00000000000000 -4.44089209850063e-16]
[ 1.31957381564014e-16  1.41622049084608e-16 -6.68515202578511e-17 -3.95597468756028e-17 -4.85722573273506e-17 -5.32388011580111e-17 -1.31328455615552e-16      1.00000000000000]
[    -1.00000000000000     0.000000000000000     0.000000000000000  4.85722573273506e-17     0.000000000000000 -5.55111512312578e-17 -1.11022302462516e-16  2.22044604925031e-16]
[    0.000000000000000     -1.00000000000000     0.000000000000000 -2.77555756156289e-17  5.55111512312578e-17 -8.69223574327834e-17     0.000000000000000 -4.44089209850063e-16]
[    0.000000000000000 -1.05042437087238e-17     -1.00000000000000  3.33066907387547e-16  1.11022302462516e-16 -1.18333563634309e-16  4.40064433050777e-17  2.22044604925031e-16]
[ 5.27829526256056e-16  1.99901485752317e-16  1.65710718121313e-17     -1.00000000000000 -2.22044604925031e-16  5.52150940090699e-16 -3.93560383111738e-16  1.01155762925061e-16]
sage: F == C * E * C.transpose()
True
sage: abs(F[0, 4] - 1) < 1e-10
True
sage: abs(F[4, 0] + 1) < 1e-10
True

sage: F.parent()
Full MatrixSpace of 8 by 8 dense matrices over Real Field with 53 bits of precision
sage: C.parent()
Full MatrixSpace of 8 by 8 dense matrices over Real Field with 53 bits of precision