AndroidRemoteController/python/py/Lib/site-packages/sympy/polys/matrices/tests/test_rref.py

from sympy import ZZ, QQ, ZZ_I, EX, Matrix, eye, zeros, symbols
from sympy.polys.matrices import DM, DomainMatrix
from sympy.polys.matrices.dense import ddm_irref_den, ddm_irref
from sympy.polys.matrices.ddm import DDM
from sympy.polys.matrices.sdm import SDM, sdm_irref, sdm_rref_den

import pytest


#
# The dense and sparse implementations of rref_den are ddm_irref_den and
# sdm_irref_den. These can give results that differ by some factor and also
# give different results if the order of the rows is changed. The tests below
# show all results on lowest terms as should be returned by cancel_denom.
#
# The EX domain is also a case where the dense and sparse implementations
# can give results in different forms: the results should be equivalent but
# are not canonical because EX does not have a canonical form.
#


a, b, c, d = symbols('a, b, c, d')


qq_large_1 = DM([
[  (1,2),  (1,3),  (1,5),  (1,7), (1,11), (1,13), (1,17), (1,19), (1,23), (1,29), (1,31)],
[ (1,37), (1,41), (1,43), (1,47), (1,53), (1,59), (1,61), (1,67), (1,71), (1,73), (1,79)],
[ (1,83), (1,89), (1,97),(1,101),(1,103),(1,107),(1,109),(1,113),(1,127),(1,131),(1,137)],
[(1,139),(1,149),(1,151),(1,157),(1,163),(1,167),(1,173),(1,179),(1,181),(1,191),(1,193)],
[(1,197),(1,199),(1,211),(1,223),(1,227),(1,229),(1,233),(1,239),(1,241),(1,251),(1,257)],
[(1,263),(1,269),(1,271),(1,277),(1,281),(1,283),(1,293),(1,307),(1,311),(1,313),(1,317)],
[(1,331),(1,337),(1,347),(1,349),(1,353),(1,359),(1,367),(1,373),(1,379),(1,383),(1,389)],
[(1,397),(1,401),(1,409),(1,419),(1,421),(1,431),(1,433),(1,439),(1,443),(1,449),(1,457)],
[(1,461),(1,463),(1,467),(1,479),(1,487),(1,491),(1,499),(1,503),(1,509),(1,521),(1,523)],
[(1,541),(1,547),(1,557),(1,563),(1,569),(1,571),(1,577),(1,587),(1,593),(1,599),(1,601)],
[(1,607),(1,613),(1,617),(1,619),(1,631),(1,641),(1,643),(1,647),(1,653),(1,659),(1,661)]],
        QQ)

qq_large_2 = qq_large_1 + 10**100 * DomainMatrix.eye(11, QQ)


RREF_EXAMPLES = [
    (
        'zz_1',
         DM([[1, 2, 3]], ZZ),
         DM([[1, 2, 3]], ZZ),
         ZZ(1),
    ),

    (
        'zz_2',
         DomainMatrix([], (0, 0), ZZ),
         DomainMatrix([], (0, 0), ZZ),
         ZZ(1),
    ),

    (
        'zz_3',
        DM([[1, 2],
            [3, 4]], ZZ),
        DM([[1, 0],
            [0, 1]], ZZ),
        ZZ(1),
    ),

    (
        'zz_4',
        DM([[1, 0],
            [3, 4]], ZZ),
        DM([[1, 0],
            [0, 1]], ZZ),
        ZZ(1),
    ),

    (
        'zz_5',
        DM([[0, 2],
            [3, 4]], ZZ),
        DM([[1, 0],
            [0, 1]], ZZ),
        ZZ(1),
    ),

    (
        'zz_6',
        DM([[1, 2, 3],
            [4, 5, 6],
            [7, 8, 9]], ZZ),
        DM([[1, 0, -1],
            [0, 1,  2],
            [0, 0,  0]], ZZ),
        ZZ(1),
    ),

    (
        'zz_7',
        DM([[0, 0, 0],
            [0, 0, 0],
            [1, 0, 0]], ZZ),
        DM([[1, 0, 0],
            [0, 0, 0],
            [0, 0, 0]], ZZ),
        ZZ(1),
    ),

    (
        'zz_8',
        DM([[0, 0, 0],
            [0, 0, 0],
            [0, 0, 0]], ZZ),
        DM([[0, 0, 0],
            [0, 0, 0],
            [0, 0, 0]], ZZ),
        ZZ(1),
    ),

    (
        'zz_9',
        DM([[1, 1, 0],
            [0, 0, 2],
            [0, 0, 0]], ZZ),
        DM([[1, 1, 0],
            [0, 0, 1],
            [0, 0, 0]], ZZ),
        ZZ(1),
    ),

    (
        'zz_10',
        DM([[2, 2, 0],
            [0, 0, 2],
            [0, 0, 0]], ZZ),
        DM([[1, 1, 0],
            [0, 0, 1],
            [0, 0, 0]], ZZ),
        ZZ(1),
    ),

    (
        'zz_11',
        DM([[2, 2, 0],
            [0, 2, 2],
            [0, 0, 2]], ZZ),
        DM([[1, 0, 0],
            [0, 1, 0],
            [0, 0, 1]], ZZ),
        ZZ(1),
    ),

    (
        'zz_12',
        DM([[ 1,  2,  3],
            [ 4,  5,  6],
            [ 7,  8,  9],
            [10, 11, 12]], ZZ),
        DM([[1,  0, -1],
            [0,  1,  2],
            [0,  0,  0],
            [0,  0,  0]], ZZ),
        ZZ(1),
    ),

    (
        'zz_13',
        DM([[ 1,  2,  3],
            [ 4,  5,  6],
            [ 7,  8,  9],
            [10, 11, 13]], ZZ),
        DM([[ 1,  0,  0],
            [ 0,  1,  0],
            [ 0,  0,  1],
            [ 0,  0,  0]], ZZ),
        ZZ(1),
    ),

    (
        'zz_14',
        DM([[1, 2,  4, 3],
            [4, 5, 10, 6],
            [7, 8, 16, 9]], ZZ),
        DM([[1, 0, 0, -1],
            [0, 1, 2,  2],
            [0, 0, 0,  0]], ZZ),
        ZZ(1),
    ),

    (
        'zz_15',
        DM([[1, 2,  4, 3],
            [4, 5, 10, 6],
            [7, 8, 17, 9]], ZZ),
        DM([[1, 0, 0, -1],
            [0, 1, 0,  2],
            [0, 0, 1,  0]], ZZ),
        ZZ(1),
    ),

    (
        'zz_16',
        DM([[1, 2, 0, 1],
            [1, 1, 9, 0]], ZZ),
        DM([[1, 0, 18, -1],
            [0, 1, -9,  1]], ZZ),
        ZZ(1),
    ),

    (
        'zz_17',
        DM([[1, 1, 1],
            [1, 2, 2]], ZZ),
        DM([[1, 0, 0],
            [0, 1, 1]], ZZ),
        ZZ(1),
    ),

    (
        # Here the sparse implementation and dense implementation give very
        # different denominators: 4061232 and -1765176.
        'zz_18',
        DM([[94, 24,  0, 27, 0],
            [79,  0,  0,  0, 0],
            [85, 16, 71, 81, 0],
            [ 0,  0, 72, 77, 0],
            [21,  0, 34,  0, 0]], ZZ),
        DM([[ 1,  0,  0,  0, 0],
            [ 0,  1,  0,  0, 0],
            [ 0,  0,  1,  0, 0],
            [ 0,  0,  0,  1, 0],
            [ 0,  0,  0,  0, 0]], ZZ),
        ZZ(1),
    ),

    (
        # Let's have a denominator that cannot be cancelled.
        'zz_19',
        DM([[1, 2, 4],
            [4, 5, 6]], ZZ),
        DM([[3, 0, -8],
            [0, 3, 10]], ZZ),
        ZZ(3),
    ),

    (
        'zz_20',
        DM([[0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0],
            [0, 0, 0, 0, 4]], ZZ),
        DM([[0, 0, 0, 0, 1],
            [0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0]], ZZ),
        ZZ(1),
    ),

    (
        'zz_21',
        DM([[0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
            [1, 0, 0, 0, 0, 0, 1, 0, 0, 0],
            [0, 1, 0, 0, 0, 0, 0, 1, 0, 0],
            [0, 0, 0, 1, 0, 0, 0, 0, 1, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 1]], ZZ),
        DM([[1, 0, 0, 0, 0, 0, 1, 0, 0, 0],
            [0, 1, 0, 0, 0, 0, 0, 1, 0, 0],
            [0, 0, 0, 1, 0, 0, 0, 0, 1, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 1],
            [0, 0, 0, 0, 0, 1, 0, 0, 0, 0]], ZZ),
        ZZ(1),
    ),

    (
        'zz_22',
        DM([[1, 1, 1, 0, 1],
            [1, 1, 0, 1, 0],
            [1, 0, 1, 0, 1],
            [1, 1, 0, 1, 0],
            [1, 0, 0, 0, 0]], ZZ),
        DM([[1, 0, 0, 0, 0],
            [0, 1, 0, 0, 0],
            [0, 0, 1, 0, 1],
            [0, 0, 0, 1, 0],
            [0, 0, 0, 0, 0]], ZZ),
        ZZ(1),
    ),

    (
        'zz_large_1',
        DM([
[ 0,  0,  0, 81,  0,  0, 75,  0,  0,  0,  0,  0,  0, 27,  0,  0,  0,  0,  0,  0],
[ 0,  0,  0,  0,  0, 86,  0, 92, 79, 54,  0,  7,  0,  0,  0,  0, 79,  0,  0,  0],
[89, 54, 81,  0,  0, 20,  0,  0,  0,  0,  0,  0, 51,  0, 94,  0,  0, 77,  0,  0],
[ 0,  0,  0, 96,  0,  0,  0,  0,  0,  0,  0,  0, 48, 29,  0,  0,  5,  0, 32,  0],
[ 0, 70,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 60,  0,  0,  0, 11],
[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 37,  0, 43,  0,  0],
[ 0,  0,  0,  0,  0, 38, 91,  0,  0,  0,  0, 38,  0,  0,  0,  0,  0, 26,  0,  0],
[69,  0,  0,  0,  0,  0, 94,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 55],
[ 0, 13, 18, 49, 49, 88,  0,  0, 35, 54,  0,  0, 51,  0,  0,  0,  0,  0,  0, 87],
[ 0,  0,  0,  0, 31,  0, 40,  0,  0,  0,  0,  0,  0, 50,  0,  0,  0,  0, 88,  0],
[ 0,  0,  0,  0,  0,  0,  0,  0, 98,  0,  0,  0, 15, 53,  0, 92,  0,  0,  0,  0],
[ 0,  0,  0, 95,  0,  0,  0, 36,  0,  0,  0,  0,  0, 72,  0,  0,  0,  0, 73, 19],
[ 0, 65, 14, 96,  0,  0,  0,  0,  0,  0,  0,  0,  0, 90,  0,  0,  0, 34,  0,  0],
[ 0,  0,  0, 16, 39, 44,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 51,  0,  0],
[ 0, 17,  0,  0,  0, 99, 84, 13, 50, 84,  0,  0,  0,  0, 95,  0, 43, 33, 20,  0],
[79,  0, 17, 52, 99, 12, 69,  0, 98,  0, 68,  0,  0,  0,  0,  0,  0,  0,  0,  0],
[ 0,  0,  0, 82,  0, 44,  0,  0,  0, 97,  0,  0,  0,  0,  0, 10,  0,  0, 31,  0],
[ 0,  0, 21,  0, 67,  0,  0,  0,  0,  0,  4,  0, 50,  0,  0,  0, 33,  0,  0,  0],
[ 0,  0,  0,  0,  9, 42,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  8],
[ 0, 77,  0,  0,  0,  0,  0,  0,  0,  0, 34, 93,  0,  0,  0,  0, 47,  0,  0,  0]],
           ZZ),
        DM([[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 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, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 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, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 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, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 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, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 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, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 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, 1, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 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, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 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, 1, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 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, 1, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]], ZZ),
        ZZ(1),
    ),

    (
        'zz_large_2',
        DM([
[ 0,  0,  0,  0, 50,  0,  6, 81,  0,  1, 86,  0,  0, 98, 82, 94,  4,  0,  0, 29],
[ 0, 44, 43,  0, 62,  0,  0,  0, 60,  0,  0,  0,  0, 71,  9,  0, 57, 41,  0, 93],
[ 0,  0, 28,  0, 74, 89, 42,  0, 28,  0,  6,  0,  0,  0, 44,  0,  0,  0, 77, 19],
[ 0, 21, 82,  0, 30, 88,  0, 89, 68,  0,  0,  0, 79, 41,  0,  0, 99,  0,  0,  0],
[31,  0,  0,  0, 19, 64,  0,  0, 79,  0,  5,  0, 72, 10, 60, 32, 64, 59,  0, 24],
[ 0,  0,  0,  0,  0, 57,  0, 94,  0, 83, 20,  0,  0,  9, 31,  0, 49, 26, 58,  0],
[ 0, 65, 56, 31, 64,  0,  0,  0,  0,  0,  0, 52, 85,  0,  0,  0,  0, 51,  0,  0],
[ 0, 35,  0,  0,  0, 69,  0,  0, 64,  0,  0,  0,  0, 70,  0,  0, 90,  0, 75, 76],
[69,  7,  0, 90,  0,  0, 84,  0, 47, 69, 19, 20, 42,  0,  0, 32, 71, 35,  0,  0],
[39,  0, 90,  0,  0,  4, 85,  0,  0, 55,  0,  0,  0, 35, 67, 40,  0, 40,  0, 77],
[98, 63,  0, 71,  0, 50,  0,  2, 61,  0, 38,  0,  0,  0,  0, 75,  0, 40, 33, 56],
[ 0, 73,  0, 64,  0, 38,  0, 35, 61,  0,  0, 52,  0,  7,  0, 51,  0,  0,  0, 34],
[ 0,  0, 28,  0, 34,  5, 63, 45, 14, 42, 60, 16, 76, 54, 99,  0, 28, 30,  0,  0],
[58, 37, 14,  0,  0,  0, 94,  0,  0, 90,  0,  0,  0,  0,  0,  0,  0,  8, 90, 53],
[86, 74, 94,  0, 49, 10, 60,  0, 40, 18,  0,  0,  0, 31, 60, 24,  0,  1,  0, 29],
[53,  0,  0, 97,  0,  0, 58,  0,  0, 39, 44, 47,  0,  0,  0, 12, 50,  0,  0, 11],
[ 4,  0, 92, 10, 28,  0,  0, 89,  0,  0, 18, 54, 23, 39,  0,  2,  0, 48,  0, 92],
[ 0,  0, 90, 77, 95, 33,  0,  0, 49, 22, 39,  0,  0,  0,  0,  0,  0, 40,  0,  0],
[96,  0,  0,  0,  0, 38, 86,  0, 22, 76,  0,  0,  0,  0, 83, 88, 95, 65, 72,  0],
[81, 65,  0,  4, 60,  0, 19,  0,  0, 68,  0,  0, 89,  0, 67, 22,  0,  0, 55, 33]],
           ZZ),
        DM([
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 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, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 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, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 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, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 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, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 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, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 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, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 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, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 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, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 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, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]],
           ZZ),
        ZZ(1),
    ),

    (
        'zz_large_3',
        DM([
[62,35,89,58,22,47,30,28,52,72,17,56,80,26,64,21,10,35,24,42,96,32,23,50,92,37,76,94,63,66],
[20,47,96,34,10,98,19,6,29,2,19,92,61,94,38,41,32,9,5,94,31,58,27,41,72,85,61,62,40,46],
[69,26,35,68,25,52,94,13,38,65,81,10,29,15,5,4,13,99,85,0,80,51,60,60,26,77,85,2,87,25],
[99,58,69,15,52,12,18,7,27,56,12,54,21,92,38,95,33,83,28,1,44,8,29,84,92,12,2,25,46,46],
[93,13,55,48,35,87,24,40,23,35,25,32,0,19,0,85,4,79,26,11,46,75,7,96,76,11,7,57,99,75],
[128,85,26,51,161,173,77,78,85,103,123,58,91,147,38,91,161,36,123,81,102,25,75,59,17,150,112,65,77,143],
[15,59,61,82,12,83,34,8,94,71,66,7,91,21,48,69,26,12,64,38,97,87,38,15,51,33,93,43,66,89],
[74,74,53,39,69,90,41,80,32,66,40,83,87,87,61,38,12,80,24,49,37,90,19,33,56,0,46,57,56,60],
[82,11,0,25,56,58,39,49,92,93,80,38,19,62,33,85,19,61,14,30,45,91,97,34,97,53,92,28,33,43],
[83,79,41,16,95,35,53,45,26,4,71,76,61,69,69,72,87,92,59,72,54,11,22,83,8,57,77,55,19,22],
[49,34,13,31,72,77,52,70,46,41,37,6,42,66,35,6,75,33,62,57,30,14,26,31,9,95,89,13,12,90],
[29,3,49,30,51,32,77,41,38,50,16,1,87,81,93,88,58,91,83,0,38,67,29,64,60,84,5,60,23,28],
[79,51,13,20,89,96,25,8,39,62,86,52,49,81,3,85,86,3,61,24,72,11,49,28,8,55,23,52,65,53],
[96,86,73,20,41,20,37,18,10,61,85,24,40,83,69,41,4,92,23,99,64,33,18,36,32,56,60,98,39,24],
[32,62,47,80,51,66,17,1,9,30,65,75,75,88,99,92,64,53,53,86,38,51,41,14,35,18,39,25,26,32],
[39,21,8,16,33,6,35,85,75,62,43,34,18,68,71,28,32,18,12,0,81,53,1,99,3,5,45,99,35,33],
[19,95,89,45,75,94,92,5,84,93,34,17,50,56,79,98,68,82,65,81,51,90,5,95,33,71,46,61,14,7],
[53,92,8,49,67,84,21,79,49,95,66,48,36,14,62,97,26,45,58,31,83,48,11,89,67,72,91,34,56,89],
[56,76,99,92,40,8,0,16,15,48,35,72,91,46,81,14,86,60,51,7,33,12,53,78,48,21,3,89,15,79],
[81,43,33,49,6,49,36,32,57,74,87,91,17,37,31,17,67,1,40,38,69,8,3,48,59,37,64,97,11,3],
[98,48,77,16,2,48,57,38,63,59,79,35,16,71,60,86,71,41,14,76,80,97,77,69,4,58,22,55,26,73],
[80,47,78,44,31,48,47,29,29,62,19,21,17,24,19,3,53,93,97,57,13,54,12,10,77,66,60,75,32,21],
[86,63,2,13,71,38,86,23,18,15,91,65,77,65,9,92,50,0,17,42,99,80,99,27,10,99,92,9,87,84],
[66,27,72,13,13,15,72,75,39,3,14,71,15,68,10,19,49,54,11,29,47,20,63,13,97,47,24,62,16,96],
[42,63,83,60,49,68,9,53,75,87,40,25,12,63,0,12,0,95,46,46,55,25,89,1,51,1,1,96,80,52],
[35,9,97,13,86,39,66,48,41,57,23,38,11,9,35,72,88,13,41,60,10,64,71,23,1,5,23,57,6,19],
[70,61,5,50,72,60,77,13,41,94,1,45,52,22,99,47,27,18,99,42,16,48,26,9,88,77,10,94,11,92],
[55,68,58,2,72,56,81,52,79,37,1,40,21,46,27,60,37,13,97,42,85,98,69,60,76,44,42,46,29,73],
[73,0,43,17,89,97,45,2,68,14,55,60,95,2,74,85,88,68,93,76,38,76,2,51,45,76,50,79,56,18],
[72,58,41,39,24,80,23,79,44,7,98,75,30,6,85,60,20,58,77,71,90,51,38,80,30,15,33,10,82,8]],
            ZZ),
        Matrix([
    [eye(29) * 2028539767964472550625641331179545072876560857886207583101,
     Matrix([ 4260575808093245475167216057435155595594339172099000182569,
              169148395880755256182802335904188369274227936894862744452,
              4915975976683942569102447281579134986891620721539038348914,
              6113916866367364958834844982578214901958429746875633283248,
              5585689617819894460378537031623265659753379011388162534838,
              359776822829880747716695359574308645968094838905181892423,
              -2800926112141776386671436511182421432449325232461665113305,
              941642292388230001722444876624818265766384442910688463158,
              3648811843256146649321864698600908938933015862008642023935,
              -4104526163246702252932955226754097174212129127510547462419,
              -704814955438106792441896903238080197619233342348191408078,
              1640882266829725529929398131287244562048075707575030019335,
              -4068330845192910563212155694231438198040299927120544468520,
              136589038308366497790495711534532612862715724187671166593,
              2544937011460702462290799932536905731142196510605191645593,
              755591839174293940486133926192300657264122907519174116472,
              -3683838489869297144348089243628436188645897133242795965021,
              -522207137101161299969706310062775465103537953077871128403,
              -2260451796032703984456606059649402832441331339246756656334,
              -6476809325293587953616004856993300606040336446656916663680,
              3521944238996782387785653800944972787867472610035040989081,
              2270762115788407950241944504104975551914297395787473242379,
              -3259947194628712441902262570532921252128444706733549251156,
              -5624569821491886970999097239695637132075823246850431083557,
              -3262698255682055804320585332902837076064075936601504555698,
              5786719943788937667411185880136324396357603606944869545501,
              -955257841973865996077323863289453200904051299086000660036,
              -1294235552446355326174641248209752679127075717918392702116,
              -3718353510747301598130831152458342785269166356215331448279,
             ]),],
        [zeros(1, 29), zeros(1, 1)],
        ]).to_DM().to_dense(),
        ZZ(2028539767964472550625641331179545072876560857886207583101),
    ),


    (
        'qq_1',
        DM([[(1,2), 0], [0, 2]], QQ),
        DM([[1, 0], [0, 1]], QQ),
        QQ(1),
    ),

    (
        # Standard square case
        'qq_2',
        DM([[0, 1],
            [1, 1]], QQ),
        DM([[1, 0],
            [0, 1]], QQ),
        QQ(1),
    ),

    (
        # m < n  case
        'qq_3',
        DM([[1, 2, 1],
            [3, 4, 1]], QQ),
        DM([[1, 0, -1],
            [0, 1,  1]], QQ),
        QQ(1),
    ),

    (
        # same m < n  but reversed
        'qq_4',
        DM([[3, 4, 1],
            [1, 2, 1]], QQ),
        DM([[1, 0, -1],
            [0, 1,  1]], QQ),
        QQ(1),
    ),

    (
        # m > n case
        'qq_5',
        DM([[1, 0],
            [1, 3],
            [0, 1]], QQ),
        DM([[1, 0],
            [0, 1],
            [0, 0]], QQ),
        QQ(1),
    ),

    (
        # Example with missing pivot
        'qq_6',
        DM([[1, 0, 1],
            [3, 0, 1]], QQ),
        DM([[1, 0, 0],
            [0, 0, 1]], QQ),
        QQ(1),
    ),

    (
        # This is intended to trigger the threshold where we give up on
        # clearing denominators.
        'qq_large_1',
        qq_large_1,
        DomainMatrix.eye(11, QQ).to_dense(),
        QQ(1),
    ),

    (
        # This is intended to trigger the threshold where we use rref_den over
        # QQ.
        'qq_large_2',
        qq_large_2,
        DomainMatrix.eye(11, QQ).to_dense(),
        QQ(1),
    ),

    (
        # Example with missing pivot and no replacement

        # This example is just enough to show a different result from the dense
        # and sparse versions of the algorithm:
        #
        #   >>> A = Matrix([[0, 1], [0, 2], [1, 0]])
        #   >>> A.to_DM().to_sparse().rref_den()[0].to_Matrix()
        #   Matrix([
        #   [1, 0],
        #   [0, 1],
        #   [0, 0]])
        #   >>> A.to_DM().to_dense().rref_den()[0].to_Matrix()
        #   Matrix([
        #   [2, 0],
        #   [0, 2],
        #   [0, 0]])
        #
        'qq_7',
        DM([[0, 1],
            [0, 2],
            [1, 0]], QQ),
        DM([[1, 0],
            [0, 1],
            [0, 0]], QQ),
        QQ(1),
    ),

    (
        # Gaussian integers
        'zz_i_1',
        DM([[(0,1), 1, 1],
            [    1, 1, 1]], ZZ_I),
        DM([[1, 0, 0],
            [0, 1, 1]], ZZ_I),
        ZZ_I(1),
    ),

    (
        # EX: test_issue_23718
        'EX_1',
        DM([
        [a, b, 1],
        [c, d, 1]], EX),
        DM([[a*d - b*c,         0, -b + d],
            [        0, a*d - b*c,  a - c]], EX),
        EX(a*d - b*c),
    ),

]


def _to_DM(A, ans):
    """Convert the answer to DomainMatrix."""
    if isinstance(A, DomainMatrix):
        return A.to_dense()
    elif isinstance(A, Matrix):
        return A.to_DM(ans.domain).to_dense()

    if not (hasattr(A, 'shape') and hasattr(A, 'domain')):
        shape, domain = ans.shape, ans.domain
    else:
        shape, domain = A.shape, A.domain

    if isinstance(A, (DDM, list)):
        return DomainMatrix(list(A), shape, domain).to_dense()
    elif isinstance(A, (SDM, dict)):
        return DomainMatrix(dict(A), shape, domain).to_dense()
    else:
        assert False # pragma: no cover


def _pivots(A_rref):
    """Return the pivots from the rref of A."""
    return tuple(sorted(map(min, A_rref.to_sdm().values())))


def _check_cancel(result, rref_ans, den_ans):
    """Check the cancelled result."""
    rref, den, pivots = result
    if isinstance(rref, (DDM, SDM, list, dict)):
        assert type(pivots) is list
        pivots = tuple(pivots)
    rref = _to_DM(rref, rref_ans)
    rref2, den2 = rref.cancel_denom(den)
    assert rref2 == rref_ans
    assert den2 == den_ans
    assert pivots == _pivots(rref)


def _check_divide(result, rref_ans, den_ans):
    """Check the divided result."""
    rref, pivots = result
    if isinstance(rref, (DDM, SDM, list, dict)):
        assert type(pivots) is list
        pivots = tuple(pivots)
    rref_ans = rref_ans.to_field() / den_ans
    rref = _to_DM(rref, rref_ans)
    assert rref == rref_ans
    assert _pivots(rref) == pivots


@pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES)
def test_Matrix_rref(name, A, A_rref, den):
    K = A.domain
    A = A.to_Matrix()
    A_rref_found, pivots = A.rref()
    if K.is_EX:
        A_rref_found = A_rref_found.expand()
    _check_divide((A_rref_found, pivots), A_rref, den)


@pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES)
def test_dm_dense_rref(name, A, A_rref, den):
    A = A.to_field()
    _check_divide(A.rref(), A_rref, den)


@pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES)
def test_dm_dense_rref_den(name, A, A_rref, den):
    _check_cancel(A.rref_den(), A_rref, den)


@pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES)
def test_dm_sparse_rref(name, A, A_rref, den):
    A = A.to_field().to_sparse()
    _check_divide(A.rref(), A_rref, den)


@pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES)
def test_dm_sparse_rref_den(name, A, A_rref, den):
    A = A.to_sparse()
    _check_cancel(A.rref_den(), A_rref, den)


@pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES)
def test_dm_sparse_rref_den_keep_domain(name, A, A_rref, den):
    A = A.to_sparse()
    A_rref_f, den_f, pivots_f = A.rref_den(keep_domain=False)
    A_rref_f = A_rref_f.to_field() / den_f
    _check_divide((A_rref_f, pivots_f), A_rref, den)


@pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES)
def test_dm_sparse_rref_den_keep_domain_CD(name, A, A_rref, den):
    A = A.to_sparse()
    A_rref_f, den_f, pivots_f = A.rref_den(keep_domain=False, method='CD')
    A_rref_f = A_rref_f.to_field() / den_f
    _check_divide((A_rref_f, pivots_f), A_rref, den)


@pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES)
def test_dm_sparse_rref_den_keep_domain_GJ(name, A, A_rref, den):
    A = A.to_sparse()
    A_rref_f, den_f, pivots_f = A.rref_den(keep_domain=False, method='GJ')
    A_rref_f = A_rref_f.to_field() / den_f
    _check_divide((A_rref_f, pivots_f), A_rref, den)


@pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES)
def test_ddm_rref_den(name, A, A_rref, den):
    A = A.to_ddm()
    _check_cancel(A.rref_den(), A_rref, den)


@pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES)
def test_sdm_rref_den(name, A, A_rref, den):
    A = A.to_sdm()
    _check_cancel(A.rref_den(), A_rref, den)


@pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES)
def test_ddm_rref(name, A, A_rref, den):
    A = A.to_field().to_ddm()
    _check_divide(A.rref(), A_rref, den)


@pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES)
def test_sdm_rref(name, A, A_rref, den):
    A = A.to_field().to_sdm()
    _check_divide(A.rref(), A_rref, den)


@pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES)
def test_ddm_irref(name, A, A_rref, den):
    A = A.to_field().to_ddm().copy()
    pivots_found = ddm_irref(A)
    _check_divide((A, pivots_found), A_rref, den)


@pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES)
def test_ddm_irref_den(name, A, A_rref, den):
    A = A.to_ddm().copy()
    (den_found, pivots_found) = ddm_irref_den(A, A.domain)
    result = (A, den_found, pivots_found)
    _check_cancel(result, A_rref, den)


@pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES)
def test_sparse_sdm_rref(name, A, A_rref, den):
    A = A.to_field().to_sdm()
    _check_divide(sdm_irref(A)[:2], A_rref, den)


@pytest.mark.parametrize('name, A, A_rref, den', RREF_EXAMPLES)
def test_sparse_sdm_rref_den(name, A, A_rref, den):
    A = A.to_sdm().copy()
    K = A.domain
    _check_cancel(sdm_rref_den(A, K), A_rref, den)