This chapter documents various functions which enhance **GAP3**'s ability
to work with matrices.

- DecomposedMat
- BlocksMat
- RepresentativeDiagonalConjugation
- ProportionalityCoefficient
- ExteriorPower
- SymmetricPower
- SchurFunctor
- IsNormalizing
- IndependentLines
- OnMatrices
- PermMatMat
- BigCellDecomposition

`DecomposedMat( `

`mat` )

Finds if the square matrix `mat` with zeroes (or `false`

) in symmetric
positions admits a block decomposition.

Define a graph `G` with vertices `[1..Length(mat)]`

and with an edge
between `i`

and `j`

if either `mat[i][j]`

or `mat[j][i]`

is non-zero.
`DecomposedMat`

return a list of lists `l`

such that `l[1],l[2]`

, etc.. are
the vertices in each connected component of `G`. In other words, the
matrices `mat{l[1]}{l[1]},mat{l[2]}{l[2]}`

, etc... are blocks of
the matrix `mat`. This function may also be applied to boolean matrices
where non-zero is then replaced by `true`

.

gap> m := [ [ 0, 0, 0, 1 ], > [ 0, 0, 1, 0 ], > [ 0, 1, 0, 0 ], > [ 1, 0, 0, 0 ] ];; gap> DecomposedMat( m ); [ [ 1, 4 ], [ 2, 3 ] ] gap> PrintArray( m{[ 1, 4 ]}{[ 1, 4 ]}); [[0, 1], [1, 0]]

`Blocks( `

`M` )

Finds if the matrix `M` admits a block decomposition.

Define a bipartite graph `G` with vertices `[1..Length(M)]`

,
`[1..Length(M[1])]`

and with an edge between `i`

and `j`

if `M[i][j]`

is
not zero. BlocksMat returns a list of pairs of lists `I`

such that
`[I[1][1],I[1][2]]`

, etc.. are the vertices in each connected component of
`G`. In other words, `M{I[1][1]}{I[1][2]}`

, `M{I[2][1]}{I[2][2]}`

,etc...
are blocks of `M`

.

This function may also be applied to boolean matrices
where non-zero is then replaced by `true`

.

gap> m:=[ [ 1, 0, 0, 0 ], [ 0, 1, 0, 0 ], [ 1, 0, 1, 0 ], > [ 0, 0, 0, 1 ], [ 0, 0, 1, 0 ] ];; gap> BlocksMat(m); [ [ [ 1, 3, 5 ], [ 1, 3 ] ], [ [ 2 ], [ 2 ] ], [ [ 4 ], [ 4 ] ] ] gap> PrintArray(m{[1,3,5]}{[1,3]}); [[1, 0], [1, 1], [0, 1]]

`RepresentativeDiagonalConjugation( `

`M`, `N` )

`M` and `N` must be square matrices. This function returns a list `d`
such that `N=M^DiagonalMat(d)`

if such a list exists, and false
otherwise.

gap> M:=[[1,2],[2,1]]; [ [ 1, 2 ], [ 2, 1 ] ] gap> N:=[[1,4],[1,1]]; [ [ 1, 4 ], [ 1, 1 ] ] gap> RepresentativeDiagonalConjugation(M,N); [ 1, 2 ]

`ProportionalityCoefficient( `

`v`, `w` )

`v` and `w` should be two vectors of the same length. The function
returns a scalar `c` such that `v=c*w`

if such a scalar exists, and
`false`

otherwise.

gap> ProportionalityCoefficient([1,2],[2,4]); 1/2 gap> ProportionalityCoefficient([1,2],[2,3]); false

`ExteriorPower( `

`mat`, `n` )

`mat` should be a square matrix. The function returns the `n`-th exterior
power of `mat`, in the basis naturally indexed by `Combinations([1..r],n)`

,
where `r=Length(<mat>)`

.

gap> M:=[[1,2,3,4],[2,3,4,1],[3,4,1,2],[4,1,2,3]]; [ [ 1, 2, 3, 4 ], [ 2, 3, 4, 1 ], [ 3, 4, 1, 2 ], [ 4, 1, 2, 3 ] ] gap> ExteriorPower(M,2); [ [ -1, -2, -7, -1, -10, -13 ], [ -2, -8, -10, -10, -12, 2 ], [ -7, -10, -13, 1, 2, 1 ], [ -1, -10, 1, -13, 2, 7 ], [ -10, -12, 2, 2, 8, 10 ], [ -13, 2, 1, 7, 10, -1 ] ]

`SymmetricPower( `

`mat`, `n` )

`mat` should be a square matrix. The function returns the `n`-th symmetric
power of `mat`, in the basis naturally indexed by `UnorderedTuples([1..r],n)`

,
where `r=Length(<mat>)`

.

gap> M:=[[1,2],[3,4]]; [ [ 1, 2 ], [ 3, 4 ] ] gap> SymmetricPower(M,2); [ [ 1, 2, 4 ], [ 6, 10, 16 ], [ 9, 12, 16 ] ]

`SchurFunctor(`

`mat`,`l`)

`mat` should be a square matrix and `l` a partition. The result is the
Schur functor of the matrix `mat` corresponding to partition `l`; for
example, if `l=[n]`

it returns the n-th symmetric power and if `l=[1,1,1]`

it returns the 3rd exterior power. The current algorithm (from Littlewood)
is rather inefficient so it is quite slow for partitions of *n* where *n>6*.

gap> m:=CartanMat("A",3); [ [ 2, -1, 0 ], [ -1, 2, -1 ], [ 0, -1, 2 ] ] gap> SchurFunctor(m,[2,2]); [ [ 10, 12, -16, 16, -16, 12 ], [ 3/2, 9, -6, 4, -2, 1 ], [ -4, -12, 16, -16, 8, -4 ], [ 2, 4, -8, 16, -8, 4 ], [ -4, -4, 8, -16, 16, -12 ], [ 3/2, 1, -2, 4, -6, 9 ] ]

`IsNormalizing( `

`lst`, `mat` )

returns true or false according to whether the matrix `mat` leaves the
vectors in `lst` as a set invariant, i.e., `Set(l * M) = Set( l )`

.

gap> a := [ [ 1, 2 ], [ 3, 1 ] ];; gap> l := [ [ 1, 0 ], [ 0, 1 ], [ 1, 1 ], [ 0, 0 ] ];; gap> l * a; [ [ 1, 2 ], [ 3, 1 ], [ 4, 3 ], [ 0, 0 ] ] gap> IsNormalizing( l, a ); false

`IndependentLines( `

`M` )

Returns the smallest (for lexicographic order) subset `I` of `[1..Length(M)]`

such that the rank of `M{I}`

is equal to the rank of `M`.

gap> M:=CartanMat(ComplexReflectionGroup(31)); [ [ 2, 1+E(4), 1-E(4), -E(4), 0 ], [ 1-E(4), 2, 1-E(4), -1, -1 ], [ 1+E(4), 1+E(4), 2, 0, -1 ], [ E(4), -1, 0, 2, 0 ], [ 0, -1, -1, 0, 2 ] ] gap> IndependentLines(M); [ 1, 2, 4, 5 ]

`OnMatrices( `

`M` , `p`)

Effects the simultaneous permutation of the lines and columns of the matrix
`M` specified by the permutation `p`.

gap> M:=DiagonalMat([1,2,3]); [ [ 1, 0, 0 ], [ 0, 2, 0 ], [ 0, 0, 3 ] ] gap> OnMatrices(M,(1,2,3)); [ [ 3, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 2 ] ]

`PermMatMat( `

`M` , `N` [, `l1`, `l2`])

`M` and `N` should be symmetric matrices. `PermMatMat`

returns a
permutation `p` such that `OnMatrices(M,p)=N`

if such a permutation
exists, and `false`

otherwise. If list arguments `l1` and `l2` are
given, the permutation `p` should also satisfy `Permuted(l1,p)=l2`

.

This routine is useful to identify two objects which are isomorphic but
with different labelings. It is used in **CHEVIE** to identify Cartan
matrices and Lusztig Fourier transform matrices with standard
(classified) data. The program uses sophisticated algorithms, and can
often handle matrices up to *80× 80*.

gap> M:=CartanMat("D",12);; gap> p:=Random(SymmetricGroup(12)); ( 1,12, 7, 5, 9, 8, 3, 6)( 2,10)( 4,11) gap> N:=OnMatrices(M,p);; gap> PermMatMat(M,N); ( 1,12, 7, 5, 9, 8, 3, 6)( 2,10)( 4,11)

`BigCellDecomposition(M [, b])`

`M` should be a square matrix, and `b` specifies a block structure for a
matrix of same size as `M` (it is a list of lists whose union is
`[1..Length(M)]`

). If `b` is not given, the trivial block structure
`[[1],..,[Length(M)]]`

is assumed.

The function decomposes `M` as a product *P _{1} L P* where

`[P,L]`

; else the result is the triple `[P1,L,P]`

. The only
condition for this decomposition of

gap> q:=X(Rationals);;q.name:="q";; gap> M:= [ [ q^6, q^0, q^3, q^3, q^5 + q, q^4 + q^2 ], > [ q^0, q^6, q^3, q^3, q^5 + q, q^4 + q^2 ], > [ q^3, q^3, q^6, q^0, q^4 + q^2, q^5 + q ], > [ q^3, q^3, q^0, q^6, q^4 + q^2, q^5 + q ], > [ q^5 + q, q^5 + q, q^4 + q^2, q^4 + q^2, q^6 + q^4 + q^2 + 1, > q^5 + 2*q^3 + q ], > [ q^4 + q^2, q^4 + q^2, q^5 + q, q^5 + q, q^5 + 2*q^3 + q, > q^6 + q^4 + q^2 + 1 ] ];; gap> bb:=[ [ 2 ], [ 4 ], [ 6 ], [ 3, 5 ], [ 1 ] ];; gap> PL:=BigCellDecomposition(M,bb); [ [ [ q^0, 0*q^0, 0*q^0, 0*q^0, 0*q^0, 0*q^0 ], [ q^(-6), q^0, q^(-3), q^(-3), q^(-1) + q^(-5), q^(-2) + q^(-4) ], [ 0*q^0, 0*q^0, q^0, 0*q^0, 0*q^0, 0*q^0 ], [ q^(-3), 0*q^0, 0*q^0, q^0, q^(-2), q^(-1) ], [ q^(-1), 0*q^0, 0*q^0, 0*q^0, q^0, 0*q^0 ], [ q^(-2), 0*q^0, q^(-1), 0*q^0, q^(-1), q^0 ] ], [ [ q^6 - q^4 - 1 + q^(-2), 0*q^0, 0*q^0, 0*q^0, 0*q^0, 0*q^0 ], [ 0*q^0, q^6, 0*q^0, 0*q^0, 0*q^0, 0*q^0 ], [ 0*q^0, 0*q^0, q^6 - q^4 - 1 + q^(-2), 0*q^0, 0*q^0, 0*q^0 ], [ 0*q^0, 0*q^0, 0*q^0, q^6 - 1, 0*q^0, 0*q^0 ], [ 0*q^0, 0*q^0, 0*q^0, 0*q^0, q^6 - q^4 - 1 + q^(-2), 0*q^0 ], [ 0*q^0, 0*q^0, 0*q^0, 0*q^0, 0*q^0, q^6 - 1 ] ] ] gap> M=TransposedMat(PL[1])*PL[2]*PL[1]; true

gap3-jm

19 Feb 2018