# Checkerboard the Matrix

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:

• Great challenge! It might be nice to have a sample case where an existing 0 needs to become non-zero in the final output. Commented Jul 29, 2020 at 20:05
• @HyperNeutrino Good idea. I also added a separate one with a negative entry. Commented Jul 29, 2020 at 20:57
• @user "You may assume that it is possible to express the given matrix in checkerboard form." For a matrix with linearly independent rows and at least as many rows as columns, it is always possible (express the matrix in reduced row echelon form, then add odd rows to odd rows and even rows to even rows). If there are fewer rows than columns, checkerboarding requires more care. Commented Aug 4, 2020 at 19:01
• Congratulations on winning the Trickiest Challenge category for Best of 2020 (codegolf.meta.stackexchange.com/q/20638/68942) for this challenge! I will be awarding a +500 bounty for this award. Which answer would you like it to be given to? Commented Feb 23, 2021 at 19:14
• @HyperNeutrino Interesting category, and I'm surprised no one has answered this question yet. The bounty should go to https://codegolf.stackexchange.com/a/209201/68261 Commented Feb 26, 2021 at 0:28

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

• Welcome to Code Golf, and nice first answer! Is it possible to edit in a link to an online testing environment so that others can test your program? For example, while it doesn't have Matlab, Try it online does host Octave Commented Mar 24, 2021 at 14:28
• @ChartZBelatedly weren't you giving a bounty on answers to good old unanswered questions? Does this answer qualify? Commented Mar 24, 2021 at 15:53
• @Wasif Not quite, mine is for questions with a score of less than 15. This one by JoKing however, I think this answer would qualify for Commented Mar 24, 2021 at 16:23
• Poor answerer ;-( Commented Mar 24, 2021 at 16:29
• "You may assume that the rows of the matrix are linearly independent," which means that form 3 cannot happen. That might provide an opportunity for further golfing. Commented Mar 24, 2021 at 16:46

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