19
\$\begingroup\$

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:

\$\endgroup\$
8
  • 1
    \$\begingroup\$ Great challenge! It might be nice to have a sample case where an existing 0 needs to become non-zero in the final output. \$\endgroup\$ – hyper-neutrino Jul 29 '20 at 20:05
  • 2
    \$\begingroup\$ @HyperNeutrino Good idea. I also added a separate one with a negative entry. \$\endgroup\$ – fireflame241 Jul 29 '20 at 20:57
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – fireflame241 Aug 4 '20 at 19:01
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – hyper-neutrino Feb 23 at 19:14
  • 1
    \$\begingroup\$ @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 \$\endgroup\$ – fireflame241 Feb 26 at 0:28
5
\$\begingroup\$

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.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – caird coinheringaahing Mar 24 at 14:28
  • \$\begingroup\$ @ChartZBelatedly weren't you giving a bounty on answers to good old unanswered questions? Does this answer qualify? \$\endgroup\$ – Wasif Mar 24 at 15:53
  • \$\begingroup\$ @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 \$\endgroup\$ – caird coinheringaahing Mar 24 at 16:23
  • \$\begingroup\$ Poor answerer ;-( \$\endgroup\$ – Wasif Mar 24 at 16:29
  • 2
    \$\begingroup\$ "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. \$\endgroup\$ – fireflame241 Mar 24 at 16:46

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.