11
\$\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

Related:

\$\endgroup\$
  • 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\$ – HyperNeutrino Jul 29 at 20:05
  • 2
    \$\begingroup\$ @HyperNeutrino Good idea. I also added a separate one with a negative entry. \$\endgroup\$ – fireflame241 Jul 29 at 20:57
  • \$\begingroup\$ Is it always possible for a row-equivalent checkerboard matrix to be created? \$\endgroup\$ – user Aug 4 at 18:07
  • 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 at 19:01

Your Answer

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

Browse other questions tagged or ask your own question.