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