# Creation of Sparse Matrices This section describes the constructs provided for creating sparse matrices. ## Construction of Initialized Sparse Matrices ### `SparseMatrix(R, m, n, Q): Rng, RngIntElt, RngIntElt, [ ] -> MtrxSprs` ### `SparseMatrix(m, n, Q): RngIntElt, RngIntElt, [ ] -> MtrxSprs` Given a ring $R$ (optional), integers $m,n\ge 0$ and a sequence $Q$, return the $m\times n$ sparse matrix over $R$ whose non-zero entries are those specified by $Q$, coerced into $R$. If $R$ is not given, it is derived from the entries in $Q$. Either of $m$ and $n$ may be 0, in which case $Q$ must have length 0 (and may be null if $R$ is given), and the $m\times n$ zero sparse matrix over $R$ is returned. There are two possibilities for $Q$: **(a)** The sequence $Q$ is a sequence of tuples, each of the form ``, where $1\leq i\leq m$, $1\leq j\leq n$, and $x\in S$ for some ring $S$. Such a tuple specifies that the $(i, j)$-th entry of the matrix is $x$. If $R$ is given, then $x$ is coerced into $R$; otherwise the matrix is created over $S$. If an entry position is not given then its value is zero, while if an entry position is repeated then the last value overrides any previous values. **(b)** The sequence $Q$ is a “flat” sequence of integers, giving the entries of the matrix in compact form. To be precise, $Q$ begins with the number of non-zero entries $n$ for the first row, then $2\cdot n$ integers giving column-entry pairs for the first row, and this format is immediately followed for the second row and so on. A zero row is specified by a zero value for $n$. If $R$ is given, the integer entries are coerced into $R$; otherwise the matrix is defined over ${\mathbb{Z}}$. (Thus this method will not allow elements of $R$ which cannot be created by coercing integers into $R$ alone; another way of saying this is that the entries must all lie in the prime ring of $R$). This allows a very compact way to create (and store) sparse matrices. The examples below illustrate this format. ### `SparseMatrix(R, m, n): Rng, RngIntElt, RngIntElt -> MtrxSprs` Given a ring $R$, and integers $m,n\ge 0$, create the $m\times n$ sparse matrix over $R$. ### `SparseMatrix(m, n): RngIntElt, RngIntElt -> MtrxSprs` Given integers $m,n\ge 0$, create the $m\times n$ sparse matrix over the integer ring ${\mathbb{Z}}$. ## Construction of Trivial Sparse Matrices ### `SparseMatrix(R): Rng -> MtrxSprs` ### `SparseMatrix() -> MtrxSprs` Create the $0\times 0$ sparse matrix over $R$. If $R$ is omitted (so there are no arguments), then $R$ is taken to be the integer ring ${\mathbb{Z}}$. These functions will usually be called when the user wishes to create a sparse matrix whose final dimensions are initially unknown, and for which the [`SetEntry`](entries.md#function-smat-setentry) procedure below will be used to extend the matrix automatically, as needed. ### `Example: Create (ex-a5eec8)` This example demonstrates simple ways of creating matrices using the general `SparseMatrix(R, m, n, Q)` function. Sparse matrices may be displayed in the sparse representation using the `Magma` print-format. Also, the function [`Matrix`](conversion.md#function-smat-matrix) (described below) takes a sparse matrix and returns a normal (dense-representation) matrix, so this function provides a means of printing a small sparse matrix as a normal matrix. (a) A sparse $2 \times 2$ matrix is defined over ${\mathbb{Z}}$, using the first (sequence of tuples) method. We specify that there is a $3$ in the $(1,2)$ position and a $-1$ in the $(2,3)$ position. The ring need not be given since the entries are in ${\mathbb{Z}}$ already. ```magma > A := SparseMatrix(2, 3, [<1,2,3>, <2,3,-1>]); > A; Sparse matrix with 2 rows and 3 columns over Integer Ring > Matrix(A); [ 0 3 0] [ 0 0 -1] ``` (b) The same matrix is now defined over ${\bf F}_{23}$. We could also coerce the 3rd component of each tuple into ${\bf F}_{23}$ and thus omit the first argument. ```magma > A := SparseMatrix(GF(23), 2, 3, [<1,2,3>, <2,3,-1>]); > A; Sparse matrix with 2 rows and 3 columns over GF(23) > Matrix(A); [ 0 3 0] [ 0 0 22] ``` (c) A similar sparse matrix is defined over ${\bf F}_{2^4}$. When $A$ is printed in `Magma` format, the sequence-of-tuples form is used (because the entries cannot be printed as integers). ```magma > K := GF(2^4); > A := SparseMatrix(K, 2, 3, [<1,2,3>, <2,3,w>]); > A; Sparse matrix with 2 rows and 3 columns over GF(2^4) > Matrix(A); [ 0 1 0] [ 0 0 w] > A: Magma; SparseMatrix(GF(2, 4), 2, 3, [ <1, 2, 1>, <2, 3, w> ]) ``` (d) A sparse $4 \times 5$ matrix $A$ is defined over ${\mathbb{Z}}$, using the second (flat integer sequence) method. Here row 1 has one non-zero entry: -1 at column 3; then row 2 has three non-zero entries: 9 at column 2, 7 at column 3, and $-3$ at column 4; row 3 has no non-zero entries (so we give a 0 at this point); and finally row 4 has one non-zero entry $3$ at column 4. Note that when $A$ is printed in `Magma` format, this time the compact “flat” sequence of integers form is used, since this is possible. ```magma > A := SparseMatrix(4,5, [1,3,-1, 3,2,9,3,7,4,-3, 0, 1,4,3]); > A; Sparse matrix with 4 rows and 5 columns over Integer Ring > Matrix(A); [ 0 0 -1 0 0] [ 0 9 7 -3 0] [ 0 0 0 0 0] [ 0 0 0 3 0] > A: Magma; SparseMatrix(4, 5, \\[ 1, 3,-1, 3, 2,9, 3,7, 4,-3, 0, 1, 4,3 ]) ``` ## Construction of Structured Matrices ### `IdentitySparseMatrix(R, n): Rng, RngElt -> MtrxSprs` Given a ring $R$, and an integer $n\ge 0$, return the $n\times n$ identity sparse matrix over $R$. ### `ScalarSparseMatrix(n, s): RngIntElt, RngElt -> MtrxSprs` Given an integer $n\ge 0$ and an element $s$ of a ring $R$, return the $n \times n$ scalar sparse matrix over $R$ which has $s$ on the diagonal and zeros elsewhere. The argument $n$ may be 0, in which case the $0 \times 0$ sparse matrix over $R$ is returned. ### `ScalarSparseMatrix(R, n, s): Rng, RngIntElt, RngElt -> MtrxSprs` Given a ring $R$, an integer $n\ge 0$ and an element $s$ of a ring $S$, return the $n \times n$ scalar sparse matrix over $R$ which has $s$, coerced into $R$, on the diagonal and zeros elsewhere. $n$ may be 0, in which case in which case the $0 \times 0$ sparse matrix over $R$ is returned. ### `DiagonalSparseMatrix(R, n, Q): Rng, RngIntElt, [ RngElt ] -> MtrxSprs` Given a ring $R$, an integer $n\ge 0$ and a sequence $Q$ of $n$ ring elements, return the $n \times n$ diagonal sparse matrix over $R$ whose diagonal entries correspond to the entries of $Q$, coerced into $R$. ### `DiagonalSparseMatrix(R, Q): Rng, [ RngElt ] -> MtrxSprs` Given a ring $R$ and a sequence $Q$ of $n$ ring elements, return the $n \times n$ diagonal sparse matrix over $R$ whose diagonal entries correspond to the entries of $Q$, coerced into $R$. ### `DiagonalSparseMatrix(Q): [ RngElt ] -> MtrxSprs` Given a sequence $Q$ of $n$ elements from a ring $R$, return the $n \times n$ diagonal sparse matrix over $R$ whose diagonal entries ### `SparseMonomialMatrix(g): GrpPermElt -> MtrxSprs` Given a degree-$(2d)$ permutation $g$, return the $d \times d$ monomial matrix corresponding to $g$. ## Parents of Sparse Matrices ### `SparseMatrixStructure(R): [ Rng ] -> MtrxSprsStr` Create the structure containing all sparse matrices (of any shape) over ring $R$. This structure does not need to be created explicitly by the user (it will be the parent of any sparse matrix over $R$), but it may be useful to create it in this way occasionally.