GAP (Utils) - Chapter 6: Matrices

In June 2023 Hongyi Zhao asked in the Forum for a function to implement matrix decomposition into blocks. Such a function was then provided by Pedro García-Sánchez. Hongyi Zhao then requested that the function be added to Utils. What is provided here is a revised version of the original solution, returning a list of decompositions.

This function is a partial inverse to the undocumented library operation DirectSumMat. So if L is the list of diagonal decompositions of a matrix M then each entry in L is a list of matrices, and the direct sum of each of these lists is equal to the original M.

In the following examples, M_6 is an obvious direct sum with 3 blocks. M_4 is an example with three decompositions, while M_8 = M_4 ⊕ M_4 has 16 decompositions (not listed).


gap> M6 := [ [1,2,0,0,0,0], [3,4,0,0,0,0], [5,6,0,0,0,0],                       
>            [0,0,9,0,0,0], [0,0,0,1,2,3], [0,0,0,4,5,6] ];;
gap> Display( M6 );
[ [  1,  2,  0,  0,  0,  0 ],
  [  3,  4,  0,  0,  0,  0 ],
  [  5,  6,  0,  0,  0,  0 ],
  [  0,  0,  9,  0,  0,  0 ],
  [  0,  0,  0,  1,  2,  3 ],
  [  0,  0,  0,  4,  5,  6 ] ]
gap> L6 := DirectSumDecompositionMatrices( M6 );
[ [ [ [ 1, 2 ], [ 3, 4 ], [ 5, 6 ] ], [ [ 9 ] ], [ [ 1, 2, 3 ], [ 4, 5, 6 ] ] 
     ] ]

gap> M4 := [ [0,3,0,0], [0,0,0,0], [0,0,0,0], [0,0,4,0] ];;
gap> Display( M4 );
[ [  0,  3,  0,  0 ],
  [  0,  0,  0,  0 ],
  [  0,  0,  0,  0 ],
  [  0,  0,  4,  0 ] ]
gap> L4 := DirectSumDecompositionMatrices( M4 );
[ [ [ [ 0, 3 ] ], [ [ 0, 0 ], [ 0, 0 ], [ 4, 0 ] ] ], 
  [ [ [ 0, 3 ], [ 0, 0 ] ], [ [ 0, 0 ], [ 4, 0 ] ] ], 
  [ [ [ 0, 3 ], [ 0, 0 ], [ 0, 0 ] ], [ [ 4, 0 ] ] ] ]
gap> for L in L4 do 
>        A := DirectSumMat( L );; 
>        if ( A = M4 ) then Print( "yes, A = M4\n" ); fi; 
>    od;
yes, A = M4
yes, A = M4
yes, A = M4

gap> M8 := DirectSumMat( M4, M4 );; 
gap> Display( M8 );
[ [  0,  3,  0,  0,  0,  0,  0,  0 ],
  [  0,  0,  0,  0,  0,  0,  0,  0 ],
  [  0,  0,  0,  0,  0,  0,  0,  0 ],
  [  0,  0,  4,  0,  0,  0,  0,  0 ],
  [  0,  0,  0,  0,  0,  3,  0,  0 ],
  [  0,  0,  0,  0,  0,  0,  0,  0 ],
  [  0,  0,  0,  0,  0,  0,  0,  0 ],
  [  0,  0,  0,  0,  0,  0,  4,  0 ] ]
gap> L8 := DirectSumDecompositionMatrices( M8 );;
gap> Length( L8 ); 
16

The current method does not, however, catch all possible decompositions. In the following example the matrix M_5 has its third row and third column extirely zero, and the only decomposition found has a [0] factor. There are clearly two 2-factor decompositions with a 2-by-3 and a 3-by-2 factor, but these are not found at present.


gap> M5 := [ [1,2,0,0,0], [3,4,0,0,0], [0,0,0,0,0],
>            [0,0,0,6,7], [0,0,0,8,9] ];;
gap> Display(M5);
[ [  1,  2,  0,  0,  0 ],
  [  3,  4,  0,  0,  0 ],
  [  0,  0,  0,  0,  0 ],
  [  0,  0,  0,  6,  7 ],
  [  0,  0,  0,  8,  9 ] ]
gap> L5 := DirectSumDecompositionMatrices( M5 ); 
[ [ [ [ 1, 2 ], [ 3, 4 ] ], [ [ 0 ] ], [ [ 6, 7 ], [ 8, 9 ] ] ] ]

6 Matrices

6.1 Some operations for matrices

6.1-1 DirectSumDecompositionMatrices