18
\$\begingroup\$

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. 0 and 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 , so the shortest code in bytes wins.

Test cases

Input Output
0 1
1 0
True
1 0 0
0 1 3
0 0 1
True
-5
True
1 0 0 0
0 1 0 -1
0 0 1 0
0 0 0 1
True
1 0
0 1
True
0 0 0
0 1 0
0 0 1
True
0 2
1 0
False
1 2 3
4 5 6
7 8 9
False
1 0 0 0
0 0 1 0
0 0 0 1
0 1 0 0
False
2 0 0
0 0 1
0 1 0
False
1 1 1
0 1 0
0 0 1
False
\$\endgroup\$
8
  • \$\begingroup\$ Multiplying a row by zero? \$\endgroup\$
    – Neil
    Nov 13, 2021 at 6:28
  • 1
    \$\begingroup\$ @Neil Yes, \$R_i \to 0R_i\$ does count as an elementary row operation, I'll add a test case for that \$\endgroup\$ Nov 13, 2021 at 6:32
  • \$\begingroup\$ Why 6th input is true ? \$\endgroup\$
    – JulStrat
    Nov 13, 2021 at 10:31
  • \$\begingroup\$ @JulStrat See my comment above to Neil; It's the row operation \$R_1 \to 0R_1\$ on \$I_3\$ \$\endgroup\$ Nov 13, 2021 at 10:40
  • 1
    \$\begingroup\$ (I'm fine with multiplying a row by 0 counting for the purposes of this challenge, but that certainly wouldn't be an elementary matrix for mathematical purposes.) \$\endgroup\$ Nov 13, 2021 at 17:47

6 Answers 6

8
\$\begingroup\$

Python 3 + numpy, 84 bytes

lambda m:sum(m!=eye(len(m)))-3*all((m*m==m)*(m@m==eye(len(m))))<2
from numpy import*

Try it online!

I'll get things started. No idea how good this is.

Criterion: If the matrix differs from the identity in one or zero places return True. Otherwise allow up to four if the matrix has only ones and zeroes and is its own inverse.

Not 100% sure this is tight.

\$\endgroup\$
6
  • 2
    \$\begingroup\$ Might this be the first bona fide use of the matrix multiplication operator in code golf? \$\endgroup\$
    – pxeger
    Nov 13, 2021 at 14:23
  • \$\begingroup\$ @pxeger It can't be, can it? I've certainly used it before, though I'm not sure my motives were entirely innocent. \$\endgroup\$
    – loopy walt
    Nov 13, 2021 at 14:39
  • \$\begingroup\$ @pxeger I have used it here. \$\endgroup\$
    – m90
    Nov 13, 2021 at 22:20
  • \$\begingroup\$ I'm not sure this is correct for matrices larger than 4x4. E.g., this 5x5 matrix with one swap (\$R_3 \leftrightarrow R_5\$). \$\endgroup\$ Nov 14, 2021 at 5:25
  • 1
    \$\begingroup\$ @ChrisBouchard That's a pecularity of the test code, not the function itself. The test code depends on the assumption that the last test case be False. tio.run/… \$\endgroup\$
    – loopy walt
    Nov 14, 2021 at 12:14
3
\$\begingroup\$

Charcoal, 41 31 bytes

⊙θ⊙謋⁼κμΣEθΣEν¬⁼π⁼ξ⎇⁼ρκμ⎇⁼ρμκρ

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - if elementary, nothing if not. Explanation: There must be a pair of rows such that the number of differences between the input and the identity matrix with the pair of rows swapped must not exceed zero if the rows are different or one if the rows are the same (i.e. there can be one difference between the input and the identity matrix).

⊙θ⊙θ                            Any two rows satisfy
      ⁼κμ                       Same rows
    ¬‹                          Is not less than
          Eθ Eι                 Map over input matrix
                 π              Current element
               ¬⁼               Does not equal
                  ⁼ξ            Identity matrix
                    ⎇⁼ρκμ⎇⁼ρμκρ With rows swapped
         Σ  Σ                   Take the sum
                                Implicitly print
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 92 bytes

Returns a Boolean value.

m=>m.some((P,p)=>m.some((Q,q)=>m.map((r,y)=>(y-p?y-q?r:P:Q).map(v=>e+=v!=!y--),e=p!=q)|e<2))

Try it online!

Commented

m =>                // m[] = input matrix
m.some((P, p) =>    // for each row P[] at position p in m[]:
  m.some((Q, q) =>  //   for each row Q[] at position q in m[]:
    m.map((r, y) => //     for each row r[] at position y in m[]:
      (             //       select the relevant row:
        y - p ?     //         if y is not equal to p:
          y - q ?   //           if y is not equal to q:
            r       //             use r[]
          :         //           else:
            P       //             use P[] (swapped with Q[])
        :           //         else:
          Q         //           use Q[] (swapped with P[])
      ).map(v =>    //       for each value v in this row:
        e +=        //         increment e if ...
          v != !y-- //           ... v is not equal to the expected
                    //           value in the identity matrix
      ),            //       end of inner map()
      e = p != q    //       start with e = 1 if two rows were
                    //       actually swapped, or 0 otherwise
    )               //     end of outer map()
    | e < 2         //     yield true if e is less than 2
  )                 //   end of inner some()
)                   // end of outer some()
\$\endgroup\$
3
\$\begingroup\$

Core Maude, 315 302 286 277 276 273 268 bytes

mod E is pr LIST{Int}. ops e i : Int ~> Int . var A B N X Y Z :[Int]. ceq e(N
X A Y B Z)= 1 if(size(X)rem N + size(Y)rem N)size(A)size(B)i(N 0)X B Y A Z =
0 N N i(N(N ^ 2)). ceq e(N X A Y)= 1 if i(N 0)X I:Int Y := i(N(N ^ 2)). eq
i(N s A)= i(N A)(0 ^(A rem s N)). endm

The result is obtained by reducing the e function with the width \$n\$ prepended to the matrix as a flattened list. The output is either the constant 1 for true, or an error term of sort [List{Int}] for false.

Example Session

Maude> --- True
> red e(
>     2
>     0 1
>     1 0
> ) .
result NzNat: 1
Maude> 
> --- True
> red e(
>     3
>     1 0 0
>     0 1 3
>     0 0 1
> ) .
result NzNat: 1
Maude> 
> --- True
> red e(
>     1
>     -5
> ) .
result NzNat: 1
Maude> 
> --- True
> red e(
>     4
>     1 0 0 0
>     0 1 0 -1
>     0 0 1 0
>     0 0 0 1
> ) .
result NzNat: 1
Maude> 
> --- True
> red e(
>     2
>     1 0
>     0 1
> ) .
result NzNat: 1
Maude> 
> --- True
> red e(
>     3
>     0 0 0
>     0 1 0
>     0 0 1
> ) .
result NzNat: 1
Maude> 
> --- False
> red e(
>     2
>     0 2
>     1 0
> ) .
result [List{Int}]: e(2 0 2 1 0)
Maude> 
> --- False
> red e(
>     3
>     1 2 3
>     4 5 6
>     7 8 9
> ) .
result [List{Int}]: e(3 1 2 3 4 5 6 7 8 9)
Maude> 
> --- False
> red e(
>     4
>     1 0 0 0
>     0 0 1 0
>     0 0 0 1
>     0 1 0 0
> ) .
result [List{Int}]: e(4 1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0)

Ungolfed

mod E is
    pr LIST{Int} .

    ops e i : Int ~> Int .

    var A B N X Y Z : [Int] .

    ceq e(N X A Y B Z) = 1
        if (size(X) rem N + size(Y) rem N) size(A) size(B) i(N 0) X B Y A Z
            = 0 N N i(N (N ^ 2)) .
    ceq e(N X A Y) = 1
        if i(N 0) X I:Int Y := i(N (N ^ 2)) .

    eq i(N s A) = i(N A) (0 ^ (A rem s N)) .
endm

We guess a partition of the input list into three or five (possibly empty) sublists, and then attempt to perform the inverse of one of the three row operations.

  • Swapping is undone by picking two rows and swapping them.
  • Multiplying and adding rows is undone by picking a single element and ignoring it — it either corresponds to the single \$1\$ in the row that was multiplied by \$\lambda\$, or the single \$1\$ in a different row that was added.

Saved 13 bytes by simplifying the identity matrix function, by recognizing that the \$1\$ occurs every \$(n + 1)\$ entries.

Saved 16 more bytes by collapsing multiplying and adding into a single case and changing the signature to only one list argument with length prepended.

Saved 9 10 more bytes by combining conditions into one list equality.

Saved 3 more bytes using 0 ^ X to do the equivalent of !x in C — i.e., convert non-zero to zero and zero to one. Maude's convention is that \$x ^ 0 = 1\$ even for \$x = 0\$.

Saved 5 more bytes by removing the base case for i and handling it in the pattern matches.

\$\endgroup\$
3
\$\begingroup\$

Desmos, 117 bytes

K=[0...W^2]
J=K[(L-0^{mod(K,W+1)})^2>0]
n(L)=L.length

f(L,W)=\{n(J)<2,32=n(\mod(J,W).\unique)^23^{L[J+1]^2}.\total\}

This turned out pretty well, considering Desmos's limitations.

The blank line indicates that the subsequent line (f(L,W)=...) should be pasted including a leading newline.

Takes input as a flattened list and the width of the matrix.

Returns 1 if the matrix is elementary, otherwise NaN (shown as "undefined")

Try it on Desmos!

How it works

It's not clear that this golfy approach works, so I'll start with a line-by-line explanation of what the code does, then give a proof of its correctness in the next section.

# K: indices of the list L, 0-indexed
#    this has one element more than L, but it gets ignored because
#    operations applied element-wise use the smallest length
K=[0...W^2]

# J: 0-indexed positions in L whose entries differ from the W×W identity matrix
J = K[ # filter K for elements where:
  (    # the corresponding entries differ from the identity matrix:
    L -            # value of L minus
    0^{mod(K,W+1)} # 1 if on main diagonal (mod(K,W+1)=0) else 0
  )^2>0 # this difference must be nonzero; (a-b)^2 > 0 ⟺ a ≠ b
]

# n: helper function to give the length
n(L)=L.length

# f: return 1 if the matrix is elementary, otherwise NaN
f(L,W) = \{
  # If 0 or 1 positions differ from the identity matrix, return 1
  n(J)<2,
  # If the following is true, return 1:
  32 = # 32 is equal to
    n(\mod(J,W).\unique)^2 * # the number of columns containing at least one entry
                             # differing from the identity matrix, squared
    3^{L[J+1]^2}.\total # the total of 3^{e_j} for each entry e_j differing from identity
\}

Proof of correctness

As observed in the other answers, "multiplying a row by a constant" and "adding a multiple of a row to another row" give either the same identity matrix (multiplying by 1 or adding 0 times a row to another row) or the identity matrix with exactly one entry changed. This is handled by n(J)<2.

The only condition left to check is swapping two rows.

Claim: 32 = n(\mod(J,W).\unique)^2 * 3^{L[J+1]^2}.\total if and only if L differs from an identity matrix by swapping two rows

Proof (backward direction): Assume L differs from an identity matrix by swapping two rows. Then exactly two columns contain entries different from the identity, so n(\mod(J,W).\unique) = 2. Additionally, the entries in L that are different than the identity must be exactly 0,0,1,1, so 3^{L[J+1]^2}.\total = 3^0 + 3^0 + 3^1 + 3^1 = 8. Hence n(\mod(J,W).\unique)^2 * 3^{L[J+1]^2}.\total = 2^2 * 8 = 32 as desired.

Proof (forwards direction): Assume 32 = n(\mod(J,W).\unique)^2 * 3^{L[J+1]^2}.\total, and assume for sake of contradiction that L does not differ from an identity matrix by swapping two rows.

Since each factor is a non-negative integer, we must have that n(\mod(J,W).\unique)^2 is a factor of 32, so n(\mod(J,W).\unique) is a factor of 4.

Case 1: Assume n(\mod(J,W).\unique)=1, so all incorrect entries are in a single column. Then we must have 3^{L[J+1]^2}.\total = 32/1^2 = 32. Since all incorrect entries are in a single column, there could be at most 1 incorrect value of 0. Hence we must have 32 written as a sum of powers of 3 with at most 1 copy of 3^0; this is impossible since 32 is 2 mod 3, contradiction.

Case 2: Assume n(\mod(J,W).\unique)=2, so all incorrect entries are in two columns. Then we must have 3^{L[J+1]^2}.\total = 32/2^2 = 8. Since all incorrect entries are in a single column, there could be at most 2 incorrect values of 0. Hence we must have 8 written as a sum of powers of 3 with at most 2 copies of 3^0: the only way to have this is 3^0 + 3^0 + 3^1 + 3^1, which can only occur when L differs from an identity matrix by swapping two rows, contradiction.

Case 3: Assume n(\mod(J,W).\unique)=4, so there are at least 4 incorrect entries. We must have 3^{L[J+1]^2}.\total = 32/4^2 = 2, but this can't happen because 3^{L[J+1]^2}.\total is the sum of at least 4 terms which are each at least 1, contradiction.

In all cases, there is a contradiction, so L must differ from an identity matrix by swapping two rows, as desired.

\$\endgroup\$
1
  • \$\begingroup\$ Wow didn't realize Desmos can do so much stuff with matrices, and also impressive proof (even if I don't fully follow what is going on) ! \$\endgroup\$
    – Aiden Chow
    May 16 at 6:34
2
\$\begingroup\$

05AB1E, 21 19 bytes

δQαDΘO0K22SQsĀ˜O!Θ~

Can probably be a golfed a bit more.. Not too happy about the ΘO0K22SQ.

Try it online or verify all test cases.

Explanation:

δQ         # Push an identity matrix of the same size as the input-matrix:
δ          #  Apply on the rows of the (implicit) input-matrix double-vectorized:
 Q         #   Equality check
α          # Take the absolute difference of the values of this identity matrix
           # with the values of the input-matrix at the same positions
 D         # Duplicate this
  ΘO0K22SQ # Check that there are exactly two rows containing exactly two 1s:
  Θ        #  Check for each value if it's equal to 1 (1 if 1; 0 otherwise)
   O       #  Sum each row to get the amount of 1s per row
    0K     #  Remove all 0s from the sums
      22SQ #  And check if this is equal to [2,2]
 s         # Swap so the duplicated list is at the top again
  Ā˜O!Θ    # Check that there are either 0 or 1 cell values changed:
  Ā        #  Check for each whether it's NOT 0 (0 if 0; 1 otherwise)
   ˜       #  Flatten the matrix
    O      #  Get the sum of this list
     !     #  Get the factorial of it (0 to 1; 1 remains 1; >=2 just becomes larger)
      Θ    #  Check if this is equal to 1
~          # Bitwise-OR to check if either of the two checks is 1
           # (after which this is output implicitly as result)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.