Accessing or Modifying Entries

The following functions and procedures enable the user to access or set individual entries of sparse matrices.

A[i]: MtrxSprs, RngIntElt -> ModTupRngElt

Given a sparse matrix \(A\) over a ring \(R\) having \(m\) rows and \(n\) columns, and an integer \(i\) such that \(1 \leq i \leq m\), return the \(i\)-th row of \(A\), as a dense vector of length \(n\) (lying in \(R^n\)).

A[i, j]: MtrxSprs, RngIntElt, RngIntElt -> RngElt

Given a sparse matrix \(A\) over a ring \(R\) having \(m\) rows and \(n\) columns, integers \(i\) and \(j\) such that \(1 \leq i \leq m\) and \(1 \leq j \leq n\), return the \((i,j)\)-th entry of \(A\), as an element of the ring \(R\).

A[i, j] := x: MtrxSprs, RngIntElt, RngIntElt, RngElt

Given a sparse matrix \(A\) over a ring \(R\) having \(m\) rows and \(n\) columns, integers \(i\) and \(j\) such that \(1 \leq i \leq m\) and \(1 \leq j \leq n\), and a ring element \(x\) coercible into \(R\), modify the \((i,j)\)-th entry of \(A\) to be \(x\). Here \(i\) and \(j\) must be within the ranges given by the current dimensions of \(A\); see SetEntry below for a procedure to automatically extend \(A\) if necessary.

SetEntry(~A, i, j, x): MtrxSprs, RngIntElt, RngIntElt, RngElt

(Procedure.) Given a sparse matrix \(A\) over a ring \(R\), integers \(i,j\geq 1\), and a ring element \(x\) coercible into \(R\), modify the \((i,j)\)-th entry of \(A\) to be \(x\). The entry specified by \(i\) and \(j\) is allowed to be beyond the current dimensions of \(A\); if so, \(A\) is automatically extended to have at least \(i\) rows and \(j\) columns.

This procedure will be commonly used in situations where the final size of the matrix is not known as an algorithm proceeds (e.g., in index-calculus methods). One can create the \(0\times 0\) sparse matrix over \({\mathbb{Z}}\), say, and then call SetEntry to build up the matrix dynamically. See the example Example: Discrete Log below, which uses this technique.

Note that extending the dimensions of \(A\) with a very large \(i\) or \(j\) will not in itself consume much memory, but if \(A\) then becomes dense or is passed to some algorithm, then the memory needed may of course be proportional to the dimensions of \(A\).

Example: Indexing (ex-167588)

This example demonstrates simple ways of accessing the entries of sparse matrices.

> 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]
> A[1];
(0 3 0)
> A[1, 3]:=5;
> A[1];
(0 3 5)

Run in calculatorCopy input

We next extend \(A\) using the procedure SetEntry.

> SetEntry(~A, 1, 5, -7);
> A;
Sparse matrix with 2 rows and 5 columns over Integer Ring
> Matrix(A);
[ 0  3  5  0 -7]
[ 0  0 -1  0  0]

Run in calculatorCopy input

A common situation is to start with the empty \(0\times 0\) matrix over \({\mathbb{Z}}\) and then to extend it dynamically.

> A := SparseMatrix();
> A;
Sparse matrix with 0 rows and 0 columns over Integer Ring
> SetEntry(~A, 1, 4, -2);
> A;
Sparse matrix with 1 row and 4 columns over Integer Ring
> SetEntry(~A, 2, 3, 8);
> A;
Sparse matrix with 2 rows and 4 columns over Integer Ring
> Matrix(A);
[ 0  0  0 -2]
[ 0  0  8  0]
> SetEntry(~A, 200, 319, 1);
> SetEntry(~A, 200, 3876, 1);
> A;
Sparse matrix with 200 rows and 3876 columns over Integer Ring
> Nrows(A);
200
> Ncols(A);
3876
> NNZEntries(A);
4
> Density(A);
0.000005159958720330237358101135190
> Support(A, 200);
[ 319, 3876 ]

Run in calculatorCopy input

Extracting and Inserting Blocks

The following functions enable the extraction of certain rows, columns or general submatrices, or the replacement of a block by another sparse matrix.

Submatrix(A, i, j, p, q): MtrxSprs, RngIntElt, RngIntElt, RngIntElt, RngIntElt -> MtrxSprs

ExtractBlock(A, i, j, p, q): MtrxSprs, RngIntElt, RngIntElt, RngIntElt, RngIntElt -> MtrxSprs

Given an \(m \times n\) sparse matrix \(A\) and integers \(i\), \(j\), \(p\) and \(q\) such that \(1\leq i \leq i + p \leq m+1\) and \(1 \leq j \leq j + q \leq n+1\), return the \(p \times q\) submatrix of \(A\) rooted at \((i, j)\). Either or both of \(p\) and \(q\) may be zero, while \(i\) may be \(m+1\) if \(p\) is zero and \(j\) may be \(n+1\) if \(q\) is zero.

SubmatrixRange(A, i, j, r, s): MtrxSprs, RngIntElt, RngIntElt, RngIntElt, RngIntElt -> MtrxSprs

ExtractBlockRange(A, i, j, r, s): MtrxSprs, RngIntElt, RngIntElt, RngIntElt, RngIntElt -> MtrxSprs

Given an \(m \times n\) sparse matrix \(A\) and integers \(i\), \(j\), \(r\) and \(s\) such that \(1\leq i\), \(i-1 \leq r \leq m\), \(1 \leq j\), and \(j-1 \leq s \leq n\), return the \(r-i+1\times s-j+1\) submatrix of \(A\) rooted at the \((i, j)\)-th entry and extending to the \((r, s)\)-th entry, inclusive. \(r\) may equal \(i-1\) or \(s\) may equal \(j-1\), in which case a sparse matrix with zero rows or zero columns, respectively, will be returned.

Submatrix(A, I, J): MtrxSprs, [RngIntElt], [RngIntElt] -> MtrxSprs

Given an \(m \times n\) sparse matrix \(A\) and integer sequences \(I\) and \(J\), return the submatrix of \(A\) given by the row indices in \(I\) and the column indices in \(J\).

InsertBlock(A, B, i, j): MtrxSprs, MtrxSprs, RngIntElt, RngIntElt -> MtrxSprs

InsertBlock(~A, B, i, j): MtrxSprs, MtrxSprs, RngIntElt, RngIntElt -> MtrxSprs

Given an \(m \times n\) sparse matrix \(A\) over a ring \(R\), a \(p \times q\) sparse matrix \(B\) over \(R\), and integers \(i\) and \(j\) such that \(1\leq i \leq i + p \leq m+1\) and \(1 \leq j \leq j + q \leq n+1\), insert \(B\) at position \((i,j)\) in \(A\). In the functional version (\(A\) is a value argument), this function returns the new sparse matrix and leaves \(A\) untouched, while in the procedural version (\(\sim A\) is a reference argument), \(A\) is modified in place so that the \(p \times q\) submatrix of \(A\) rooted at \((i, j)\) is now equal to \(B\).

RowSubmatrix(A, i, k): MtrxSprs, RngIntElt, RngIntElt -> MtrxSprs

Given an \(m \times n\) sparse matrix \(A\) and integers \(i\) and \(k\) such that \(1 \le i \leq i + k \leq m+1\), return the \(k \times n\) submatrix of \(X\) consisting of rows \([i \ldots i + k - 1]\) inclusive. The integer \(k\) may be zero and \(i\) may also be \(m+1\) if \(k\) is zero, but the result will always have \(n\) columns.

RowSubmatrix(A, i): MtrxSprs, RngIntElt -> MtrxSprs

Given an \(m \times n\) sparse matrix \(A\) and an integer \(i\) such that \(0 \le i \leq m\), return the \(i\times n\) submatrix of \(X\) consisting of the first \(i\) rows. The integer \(i\) may be \(0\), but the result will always have \(n\) columns.

RowSubmatrixRange(A, i, j): MtrxSprs, RngIntElt, RngIntElt -> MtrxSprs

Given an \(m \times n\) sparse matrix \(A\) and integers \(i\) and \(j\) such that \(1 \le i\) and \(i-1 \leq j \leq m\), return the \(j-i+1 \times n\) submatrix of \(X\) consisting of rows \([i \ldots j]\) inclusive. The integer \(j\) may equal \(i-1\), in which case a sparse matrix with zero rows and \(n\) columns will be returned.

ColumnSubmatrix(A, i, k): MtrxSprs, RngIntElt, RngIntElt -> MtrxSprs

Given an \(m \times n\) sparse matrix \(A\) and integers \(i\) and \(k\) such that \(1 \le i \leq i + k \leq n+1\), return the \(m \times k\) submatrix of \(X\) consisting of columns \([i \ldots i + k - 1]\) inclusive. The integer \(k\) may be zero and \(i\) may also be \(n+1\) if \(k\) is zero, but the result will always have \(m\) rows.

ColumnSubmatrix(A, i): MtrxSprs, RngIntElt -> MtrxSprs

Given an \(m \times n\) sparse matrix \(A\) and an integer \(i\) such that \(0 \le i \leq n\), return the \(m\times i\) submatrix of \(X\) consisting of the first \(i\) columns. The integer \(i\) may be \(0\), but the result will always have \(m\) rows.

ColumnSubmatrixRange(A, i, j): MtrxSprs, RngIntElt, RngIntElt -> MtrxSprs

Given an \(m \times n\) sparse matrix \(A\) and integers \(i\) and \(j\) such that \(1 \le i\) and \(i-1 \leq j \leq n\), return the \(m\times j-i+1\) submatrix of \(X\) consisting of columns \([i \ldots j]\) inclusive. The integer \(j\) may equal \(i-1\), in which case a sparse matrix with zero columns and \(n\) rows will be returned.

Row and Column Operations

The following functions and procedures provide elementary row or column operations on sparse matrices. For each operation, there is a corresponding function which creates a new sparse matrix for the result (leaving the input sparse matrix unchanged), and a corresponding procedure which modifies the input sparse matrix in place.

SwapRows(A, i, j): MtrxSprs, RngIntElt, RngIntElt -> MtrxSprs

SwapRows(~A, i, j): MtrxSprs, RngIntElt, RngIntElt

Given an \(m \times n\) sparse matrix \(A\) and integers \(i\) and \(j\) such that \(1 \le i\le m\) and \(1 \leq j \leq m\), swap the \(i\)-th and \(j\)-th rows of \(A\).

SwapColumns(A, i, j): MtrxSprs, RngIntElt, RngIntElt -> MtrxSprs

SwapColumns(~A, i, j): MtrxSprs, RngIntElt, RngIntElt

Given an \(m \times n\) sparse matrix \(A\) and integers \(i\) and \(j\) such that \(1 \le i\le n\) and \(1 \leq j \leq n\), swap the \(i\)-th and \(j\)-th columns of \(A\).

ReverseRows(A): MtrxSprs -> MtrxSprs

ReverseRows(~A): MtrxSprs

Given a sparse matrix \(A\), reverse all the rows of \(A\).

ReverseColumns(A): MtrxSprs -> MtrxSprs

ReverseColumns(~A): MtrxSprs

Given a sparse matrix \(A\), reverse all the columns of \(A\).

AddRow(A, c, i, j): MtrxSprs, RngElt, RngIntElt, RngIntElt -> MtrxSprs

AddRow(~A, c, i, j): MtrxSprs, RngElt, RngIntElt, RngIntElt

Given an \(m \times n\) sparse matrix \(A\) over a ring \(R\), a ring element \(c\) coercible into \(R\), and integers \(i\) and \(j\) such that \(1 \le i\le m\) and \(1 \leq j \leq m\), add \(c\) times row \(i\) of \(A\) to row \(j\) of \(A\).

AddColumn(A, c, i, j): MtrxSprs, RngElt, RngIntElt, RngIntElt -> MtrxSprs

AddColumn(~A, c, i, j): MtrxSprs, RngElt, RngIntElt, RngIntElt

Given an \(m \times n\) sparse matrix \(A\) over a ring \(R\), a ring element \(c\) coercible into \(R\), and integers \(i\) and \(j\) such that \(1 \le i\le n\) and \(1 \leq j \leq n\), add \(c\) times column \(i\) of \(A\) to column \(j\).

MultiplyRow(A, c, i): MtrxSprs, RngElt, RngIntElt -> MtrxSprs

MultiplyRow(~A, c, i): MtrxSprs, RngElt, RngIntElt

Given an \(m \times n\) sparse matrix \(A\) over a ring \(R\), a ring element \(c\) coercible into \(R\), and an integer \(i\) such that \(1 \le i\le m\), multiply row \(i\) of \(A\) by \(c\) (on the left).

MultiplyColumn(A, c, i): MtrxSprs, RngElt, RngIntElt -> MtrxSprs

MultiplyColumn(~A, c, i): MtrxSprs, RngElt, RngIntElt

Given an \(m \times n\) sparse matrix \(A\) over a ring \(R\), a ring element \(c\) coercible into \(R\), and an integer \(i\) such that \(1 \le i\le n\), multiply column \(i\) of \(A\) by \(c\) (on the left).

RemoveRow(A, i): MtrxSprs, RngIntElt -> MtrxSprs

RemoveRow(~A, i): MtrxSprs, RngIntElt

Given an \(m \times n\) sparse matrix \(A\) and an integer \(i\) such that \(1 \le i\le m\), remove row \(i\) from \(A\) (leaving an \((m-1) \times n\) sparse matrix).

RemoveColumn(A, j): MtrxSprs, RngIntElt -> MtrxSprs

RemoveColumn(~A, j): MtrxSprs, RngIntElt

Given an \(m \times n\) sparse matrix \(A\) and an integer \(j\) such that \(1 \le j\le n\), remove column \(j\) from \(A\) (leaving an \(m \times (n-1)\) sparse matrix).

RemoveRowColumn(A, i, j): MtrxSprs, RngIntElt -> MtrxSprs

RemoveRowColumn(~A, i, j): MtrxSprs, RngIntElt

Given an \(m \times n\) sparse matrix \(A\) and integers \(i\) and \(j\) such that \(1 \le i\le m\) and \(1 \le j\le n\), remove row \(i\) and column \(j\) from \(A\) (leaving an \((m-1) \times (n-1)\) sparse matrix).

RemoveZeroRows(A): MtrxSprs -> MtrxSprs

RemoveZeroRows(~A): MtrxSprs

Given a sparse matrix \(A\), remove all the zero rows of \(A\).