Core Maude, 315 302 286 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 = 0 /\ size(A)size(B)= N N /\ X B Y A Z = i(N(N ^ 2)). ceq e(N X A Y)= 1 if X I:Int Y := i(N(N ^ 2)). eq i(N 1)= 1 . eq i(N s s A)= i(N s A)(A rem s N quo 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 = 0 /\ size(A) size(B) = N N /\ X B Y A Z = i(N (N ^ 2)) . ceq e(N X A Y) = 1 if X I:Int Y := i(N (N ^ 2)) . eq i(N 1) = 1 . eq i(N s s A) = i(N s A) (A rem s N quo 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.