Consider a linear system of equations, in \$n\$ unknowns, expressed as
$$A \textbf x = \textbf b$$
where \$A \in M_{n,n}(\mathbb Z)\$ is an \$n \times n\$ matrix of integers, \$\textbf x\$ is a column vector of unknowns \$(x_1, x_2, \dots, x_n)\$ and \$\textbf b = (b_1, b_2, \dots, b_n)\$ is a column vector of integers.
We can consider the "augmented" matrix of this system as
$$A' = \begin{pmatrix} a_{11} & \cdots & a_{1n} & b_1 \\ a_{21} & \cdots & a_{2n} & b_2 \\ \vdots & \ddots & \vdots & \vdots \\ a_{n1} & \cdots & a_{nn} & b_n \end{pmatrix} $$
That is, the matrix \$A\$ but with an additional column vector \$\textbf b\$ as its final column. Let the \$i\$th row of \$A'\$ be represented as \$R_i\$
There are three elementary row operations we can do to the rows of \$A'\$ that leave the solution set \$\textbf x\$ unchanged:
- Swapping the order of two rows (\$R_i \leftrightarrow R_j\$)
- Multiplying a row by a constant \$\lambda\$ (\$R_i \to \lambda R_i\$)
- Adding a multiple of row to a given row (\$R_i \to R_i + \lambda R_j\$)
For example, we can say that the two following matrices are equivalent under these row operations:
$$ \begin{pmatrix} 7 & 0 & 0 \\ -3 & -1 & 7 \\ 8 & 0 & -9 \\ \end{pmatrix} \equiv \begin{pmatrix} 8 & 0 & -9 \\ 5 & -1 & -2 \\ 1 & 0 & 0 \\ \end{pmatrix} $$
(The specific row operations here are \$R_1 \to \frac 1 7 R_1\$, \$R_1 \leftrightarrow R_3\$, \$R_2 \to R_2 + R_1\$)
Consider the \$n\times n\$ identity matrices:
$$ I_1 = \begin{pmatrix} 1 \end{pmatrix} \\ I_2 = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \\ I_3 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \\ \vdots $$
i.e. a given cell \$(I_n)_{ij}\$ is \$1\$ if \$i = j\$ and \$0\$ otherwise.
We'll say that an integer matrix is an "elementary matrix" if it is exactly one elementary row operation away from the identity matrix. For example, the following are all elementary matrices (with the row operation shown)
$$\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \tag{$R_1 \leftrightarrow R_2$}$$ $$\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 3 \\ 0 & 0 & 1 \end{pmatrix} \tag{$R_2 \to R_2 + 3R_3$}$$ $$\begin{pmatrix} -5 \end{pmatrix} \tag{$R_1 \to -5R_1$}$$ $$\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & -1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} \tag{$R_2 \to R_2 - R_4$}$$ $$\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \tag{$R_1 \to R_1$}$$
However, none of these matrices are elementary matrices, as they all require 2 or more row operations from an identity matrix (some row operations shown):
$$\begin{pmatrix} 0 & 2 \\ 1 & 0 \end{pmatrix} \tag{$R_1 \leftrightarrow R_2$, $R_1 \to 2R_1$}$$ $$\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{pmatrix}$$ $$\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{pmatrix} \tag{$R_2 \leftrightarrow R_4$, $R_3 \leftrightarrow R_4$}$$
You are to take a square \$n \times n\$ integer matrix and indicate whether it is an elementary matrix or not. This indication can either be:
- Two consistent distinct values to indicate whether the input is or isn't an elementary matrix (e.g.
True/False,1/0,"a"/7, etc.) - Two classes of values, which are naturally interpreted as truthy and falsey values in your language (e.g.
0and non-zero integers, and empty vs non-empty list etc.)
You may take input in any standard manner or format, including taking \$n\$ as an optional input. This is code-golf, so the shortest code in bytes wins.
Test cases
| Input | Output |
|---|---|
|
True |
|
True |
|
True |
|
True |
|
True |
|
True |
|
False |
|
False |
|
False |
|
False |
|
False |
