# 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`](#function-smat-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](solution.md#example-ex-a75220) 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.

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

```

We next extend $A$ using the procedure `SetEntry`.

```magma
> 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]

```

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

```magma
> 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 ]

```

## 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$.