Checkerboard the Matrix

Question

Task

Given a matrix, your program/function should output a row-equivalent matrix in checkerboard form ( \$A_{ij}=0\$ if and only if \$i+j\$ is odd).

Two matrices are defined to be row-equivalent if and only if one can be obtained from the other by a sequence of elementary row operations (EROs), where each ERO consists of performing one of the following moves:

1. Swapping two rows
2. Multiplying one row by a nonzero rational constant
3. Adding a rational multiple of one row to another row

Since there are multiple possible outputs for each input, please include a way to verify that the output is row-equivalent to the input, or explain enough of your algorithm for it to be clear that the output is valid.

Example

Input:

2 4 6 8
0 2 0 4
1 2 5 4

Subtracting row 2 from row 3 yields

2 4 6 8
0 2 0 4
1 0 5 0

Subtracting double row 2 from row 1 yields

2 0 6 0
0 2 0 4
1 0 5 0

That is one possible output. Another possible matrix output is

1 0 3 0
0 1 0 2
1 0 4 0,

which is also row-equivalent to the given matrix and is also in checkerboard form.

Constraints

• The given matrix will have at least as many columns as rows and contain only integers (your output may use rational numbers, but this is not strictly necessary since you can multiply by a constant to obtain only integers in the output).
• You may assume that the rows of the matrix are linearly independent
• You may assume that it is possible to express the given matrix in checkerboard form

Input and output may be in any reasonable format that unambiguously represents an m×n matrix.

Sample Test Cases

Each input is followed by a possible output.

1 2 3
4 5 5
6 5 4

1 0 1
0 1 0
1 0 2


1 2 3
4 5 5
2 0 -1

1 0 1
0 1 0
1 0 2


2 4 6 8
0 2 0 4
1 2 5 4

1 0 3 0
0 1 0 2
1 0 4 0


1 2 3 2 5
6 7 6 7 6
1 2 1 2 1

1 0 1 0 1
0 1 0 1 0
1 0 2 0 3


3  2  1  10 4  18
24 31 72 31 60 19
6  8  18 9  15 7
8  4  8  20 13 36

3 0 1 0 4 0
0 1 0 5 0 9
2 0 6 0 5 0
0 8 0 9 0 7


3  2  1  10 4  18
24 31 72 31 60 19
0  4  16 -11 7 -29
8  4  8  20 13 36

3 0 1 0 4 0
0 1 0 5 0 9
2 0 6 0 5 0
0 8 0 9 0 7


1 0 0 0 -2
0 1 0 1 0
0 0 1 0 2

3 0 1 0 -4
0 2 0 2 0
5 0 3 0 -4

Related:

• Create a checkerboard matrix
• Reduced Row-Echelon Form of a Matrix

Answer 1

MATLAB - 114 129 bytes

function n=c(m)
n=rref(m);l=size(n,1);for i=1:l
e=1.5+.5*(-1)^i:2:l;N=n(e,:);n(e,:)=N+repmat(n(i,:),length(e),1).*max(N).^2;end

Try it online

For a given nxm matrix, there are three forms of the rref of the matrix.

1. The identity matrix (with optional all-zero columns) (m>=n)
2. Full rank matrix where columns that do not contain a row-leading 1 can have any value (m>n)
3. Identity matrix with zero rows on the bottom (m<n)

1 and 3 are easily made into a checkerboard by looping through each row and adding every odd/even row (which would have the 1s in the appropriate places)

for 2, however, it is impossible to make a checkerboard matrix unless the matrix is already a checkerboard. This is because the columns that have nonzero values can never be reduced because there is no column with a row-leading 1, and any ERO would add a value in another space that would ruin the checkerboard pattern. I'm certain there's a more rigorous explanation but linear algebra is not easy.

Answer 2

Python3, 941 bytes:

from math import*
E=enumerate
Z=zip
T=lambda x:[i>0 for i in x]
lcm=lambda a,b:abs((a*b)//gcd(a,b))
U=lambda i,r,m:m[:i]+[r]+m[i+1:]
G=lambda r:all(r[i+1]for i,a in E(r)if a==0 and i+1<len(r))
v=lambda m:all(not any(r[not i%2::2])and all(r[i%2::2])for i,r in E(m))
S=lambda m:sum(sum(not i for i in b)for b in m)
def f(m):
 q,Q=[m],0
 while q:
  if v(m:=q.pop(0)):return m
  for x,a in E(m):
   for y,b in E(m):
    if x<y:
     if all(j.count(0)==len(j)//2 and G(j)for j in m):q+=[m[:x]+[b]+m[x+1:y]+[a]+m[y+1:]]
     for c in[1,-1]:
      if 0 in(R:=[j+k*c for j,k in Z(a,b)]):
       if T(b)!=T(R):q+=[U(y,R,m)]
       if T(a)!=T(R):q+=[U(x,R,m)]
      for j,k in Z(a,b):
       if j and k:
        L=lcm(j,k);A=[i*(L//j)for i in a];B=[i*(L//k)for i in b]
        if 0 in(R:=[J+K*c for J,K in Z(A,B)])and T(b)!=T(R):
         if(n:=S(u:=U(y,R,m)))>Q:Q=n;q+=[u]
        if 0 in R and T(a)!=T(R):
         if(n:=S(u:=U(x,R,m)))>Q:Q=n;q+=[u]

Try it online!

A breadth-first, basic brute force approach.