# Operations on Matrices ## Arithmetic with Matrices ### `g * h: GrpMatElt, GrpMatElt -> GrpMatElt` The product of matrix $g$ and matrix $h$, where $g$ and $h$ belong to the same generic group $U$. If $g$ and $h$ both belong to the same proper subgroup $G$ of $U$, then the result will be returned as an element of $G$; if $g$ and $h$ belong to subgroups $H$ and $K$ of a subgroup $G$ of $U$ then the product is returned as an element of $G$. Otherwise, the product is returned as an element of $U$. ### `g ^ n: GrpMatElt, RngIntElt -> GrpMatElt` The $n$-th power of the matrix $g$, where $n$ is a positive or negative integer. ### `g / h: GrpMatElt, GrpMatElt -> GrpMatElt` The product of the matrix $g$ by the inverse of the matrix $h$, i.e. the element $g*h^{-1}$. Here $g$ and $h$ must belong to the same generic group $U$. The rules for determining the parent group of $g / h$ are the same as for $g*h$. ### `g ^ h: GrpMatElt, GrpMatElt -> GrpMatElt` The conjugate of the matrix $g$ by the matrix $h$, i.e. the element $h^{-1}*g*h$. Here $g$ and $h$ must belong to the same generic group $U$. The rules for determining the parent group of $g^h$ are the same as for $g*h$. ### `(g, h): GrpMatElt, GrpMatElt -> GrpMatElt` The commutator of the matrices $g$ and $h$, i.e. the element $g^{-1}*h^{-1}*g*h$. Here $g$ and $h$ must belong to the same generic group $U$. The rules for determining the parent group of $(g, h)$ are the same as those for $g*h$. ### `(g₁, ..., gᵣ): GrpMatElt, ..., GrpMatElt -> GrpMatElt` Given $r$ matrices $g_1, \ldots, g_r$ belonging to a common group, return their commutator. Commutators are *left-normed*, so they are evaluated from left to right. ### `Example: Arithmetic (ex-383e92)` These operations will be illustrated using the group ${\operatorname{GL}}(3, 4)$. ```magma > K := FiniteField(4); > GL34 := GeneralLinearGroup(3, K); > x := GL34 ! [1,w,0, 0,w,1, w^2,0,1]; > y := GL34 ! [1,0,0, 1,w,0, 1,1,w]; > x; [ 1 w 0] [ 0 w 1] [w^2 0 1] > y; [1 0 0] [1 w 0] [1 1 w] > x*y; [w^2 w^2 0] [w^2 w w] [ w 1 w] > x^10; [ w w 1] [ w 1 1] [ w w^2 w] > x^-1; [w^2 w^2 w^2] [ 1 w w] [ w w w^2] > x^y; [w^2 w^2 0] [ 0 w^2 1] [w^2 w^2 w] > x/y; [ 0 1 0] [ 0 w^2 w^2] [ w w w^2] > (x, y); [ 0 w w] [ w w^2 1] [w^2 w w^2] > (x,y,y); [w^2 w w^2] [w^2 w 0] [w^2 1 w] ``` Arithmetic with group elements is not limited to elements of finite groups. We illustrate with a group of degree 3 over a function field. ```magma > P := FunctionField(RationalField(), 7); > S := MatrixGroup< 3, P | [1,a,b,0,1,c,0,0,1], > [1,0,m,0,1,0,0,0,1], > [1,x,y,0,1,z,0,0,1] >; > > t := S.1 * S.2; > t; [ 1 a b + m] [ 0 1 c] [ 0 0 1] > t^-1; [ 1 -a a*c - b - m] [ 0 1 -c] [ 0 0 1] > Determinant(t); 1 > t^2; [ 1 2*a a*c + 2*b + 2*m] [ 0 1 2*c] [ 0 0 1] ``` ## Predicates for Matrices ### `g eq h: GrpMatElt, GrpMatElt -> BoolElt` Given matrices $g$ and $h$ belonging to the same generic group, return `true` if $g$ and $h$ are the same element, `false` otherwise. ### `g ne h: GrpMatElt, GrpMatElt -> BoolElt` Given matrices $g$ and $h$ belonging to the same generic group, return `true` if $g$ and $h$ are distinct elements, `false` otherwise. ### `IsIdentity(g): GrpMatElt -> BoolElt` ### `IsId(g): GrpMatElt -> BoolElt` Returns `true` if the matrix $g$ is the identity matrix. ### `IsScalar(g): GrpMatElt -> BoolElt` Returns `true` if the matrix $g$ is a scalar matrix. ## Matrix Invariants All of the functions for computing invariants of a square matrix apply to the elements of a matrix group. Here only operations of interest in the context of group elements are described. The reader is referred to Chapter [Matrices](../../MatricesLinearAlgebra/Matrices/index-matrices.md#chapmat) for a complete list of functions applicable to matrices. ### `Degree(g): GrpMatElt -> RngIntElt` The degree of the matrix $g$, i.e. the number of rows/columns of $g$. ### `HasFiniteOrder(g): GrpMatElt -> BoolElt, RngIntElt` Returns `true` iff the matrix $g$ has finite order. The second return value is the order if it is finite. The function rigorously proves its result (i.e., the result is not probable). Let $R$ be the ring over which $g$ is defined, and let the degree of the group in which $g$ lies be $n$. If $R$ is finite, then the first return value is trivially `true`. If $R$ is the integer ring then the function works as follows. Suppose first that $g$ has finite order $o$. By a theorem of Minkowski (see Theorem 1.4 [[Kuzmanovich and Pavlichenkov, 2002](../../references.md#cite-kuzpav2002)]), for any odd prime $p$, the reduction mod $p$ of $g$ has order $o$. Let $f(x)\in R[x]$ be the minimal polynomial of $g$. The matrix subalgebra generated by $g$ is isomorphic to the quotient ring $R[x]/\langle f(x) \rangle$, so the order $o$ of $g$ equals the order of $x$ mod $f(x)$. For arbitrary $g$, the algorithm computes the order, $\bar{o}$, of the reduction of $g$ modulo a small odd prime. If $\bar{o}$ is a possible order of an integer matrix of $g$’s dimensions (see Theorem 2.7 *op. cit.*) then this is repeated with a larger prime. If this gives a different order, or the first attempt gave an impossible order, then $g$ has infinite order. We now compute $x^{\bar{o}}\bmod f(x)$. If this is 1, then $\bar{o}$ is the order of $g$, otherwise $g$ has infinite order. If $R$ is the rational field then a necessary condition for $g$ to have finite order is that $f(x)$ has integer coefficients, thus the above algorithm applies in this case. If $R$ is an algebraic number field of degree $d$ over ${\mathbb{Q}}$ (including cyclotomic and quadratic fields), then the standard companion matrix blowup is applied to $g$ to obtain a $(nd)\times(nd)$ matrix over ${\mathbb{Q}}$, and the above algorithm is then applied to this matrix. ### `Order(g): GrpMatElt -> RngIntElt, BoolElt` ```magma Proof: BoolElt Default: true ``` Given an element $g$ of finite order belonging to a matrix group, this function returns the order of $g$. If $g$ has infinite order, a runtime error results. In the case of a matrix group over a finite field, the algorithm described in [[Celler and Leedham-Green, 1997](../../references.md#cite-clg-order)] is used. In all other cases, simple powering of $g$ is used. The parameter `Proof` is associated with the case when the coefficient ring for $g$ is a finite field. In that case, if `Proof` is set to `false`, then difficult integer factorizations will not attempted. In this situation two values are returned of which the first is a multiple $n$ of the order of $g$. and the second value indicates whether $n$ is known to be the exact order of $g$. ### `FactoredOrder(g): GrpMatElt -> [ ], BoolElt` ```magma Proof: BoolElt Default: true ``` Given an element $g$ of finite order belonging to a matrix group, this function returns the order of $g$ as a factored integer. If $g$ has infinite order, a runtime error results. If $g$ has infinite order, the function generates a runtime error. In the case of a matrix group over a finite field, the algorithm described in [[Celler and Leedham-Green, 1997](../../references.md#cite-clg-order)] is used. In all other cases, simple powering of $g$ is used. In that case it is more efficient to use this function rather than factorizing the integer returned by `Order(g)`. If $g$ has infinite order, an error ensues. If the parameter `Proof` is `false`, then difficult integer factorizations are not attempted and the first return value $F$ may contain composite numbers (so that the factorization expands to a multiple of the order of $g$); in any case the second return value indicates whether $F$ is known to be the exact factored order of $g$. ### `ProjectiveOrder(g): GrpMatElt -> RngIntElt, RngElt` ```magma Proof: BoolElt Default: true ``` The projective order $n$ of the matrix $g$, and a scalar $s$ such that $g^n = sI$. The projective order of $g$ is the smallest $n$ such that $g^n$ is a scalar matrix (not just the identity matrix), and it always divides the true order of $A$. The parameter `Proof` is as for `Order`. ### `FactoredProjectiveOrder(A): AlgMatElt -> [ ], RngElt` ```magma Proof: BoolElt Default: true ``` Given a square invertible matrix $A$ over a finite field $K$, return the projective order $n$ of $A$ in factored form and a scalar $s\in K$ such that $A^n = sI$. The parameter `Proof` is as for `FactoredOrder`. ### `CentralOrder(g : parameters): GrpMatElt -> RngIntElt, BoolElt` ### `CentralOrder(g): GrpPermElt -> RngIntElt` ```magma Proof: BoolElt Default: true ``` Return the smallest $n$ such that $g^n$ is central in its parent group. If $g$ is a matrix and the optional parameter `Proof` is `false`, then accept a multiple of this value; the second value returned is `true` if the answer is exact. ### `Determinant(g): GrpMatElt -> RngElt` The determinant of the matrix $g$. ### `Trace(g): GrpMatElt -> RngElt` The trace of the matrix $g$. ### `CharacteristicPolynomial(g: parameters): GrpMatElt -> RngPolElt` ```magma Al : MonStgElt Default: "Modular" Proof: BoolElt Default: true ``` Given a matrix $g$ belonging to a subgroup of ${\operatorname{GL}}(n, R)$, where $R$ is a field or Euclidean Domain, return the characteristic polynomial of $g$ as an element of the univariate polynomial ring over $R$. For details on the parameters, see the function `CharacteristicPolynomial` in the chapter on matrices. ### `MinimalPolynomial(g): GrpMatElt -> RngPolElt` Given a matrix $g$ belonging to a subgroup of ${\operatorname{GL}}(n, R)$, where $R$ is a field or $Z$, return the minimal polynomial of $g$ as an element of the univariate polynomial ring over $R$. ### `Example: Invariants (ex-cc263c)` We illustrate the matrix operations by applying them to some elements of ${\operatorname{GL}}(3, 4)$. ```magma > K := FiniteField(4); > GL34 := GeneralLinearGroup(3, K); > x := GL34 ! [w,0,1, 0,1,0, 1,0,1]; > x; [w 0 1] [0 1 0] [1 0 1] > Degree(x); 3 > Determinant(x); w^2 > Trace(x); w > Order(x); 15 > m := MinimalPolynomial(x); > m; t^3 + w*t^2 + w^2 > Factorization(m); [ , ] > c := CharacteristicPolynomial(x); > c; t^3 + w*t^2 + w^2 ```