laurent_r

These are some answers to the Week 257, Task 2, of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Warning: I wrote the program below and this blog post from an hospital bed in a heart intensive care unit. I think my mind is clear, but there may very well be a better way to solve the task. Also, I do not have the energy to port this Raku program to other languages, nor to provide lengthy explanations.

Task 2: Reduced Row Echelon

Given a matrix M, check whether the matrix is in reduced row echelon form.

A matrix must have the following properties to be in reduced row echelon form:

1. If a row does not consist entirely of zeros, then the first
   nonzero number in the row is a 1. We call this the leading 1.
2. If there are any rows that consist entirely of zeros, then
   they are grouped together at the bottom of the matrix.
3. In any two successive rows that do not consist entirely of zeros,
   the leading 1 in the lower row occurs farther to the right than
   the leading 1 in the higher row.
4. Each column that contains a leading 1 has zeros everywhere else
   in that column.

For example:

[
   [1,0,0,1],
   [0,1,0,2],
   [0,0,1,3]
]

The above matrix is in reduced row echelon form since the first nonzero number in each row is a 1, leading 1s in each successive row are farther to the right, and above and below each leading 1 there are only zeros.

*For more information check out this wikipedia article.

Example 1

Input: $M = [
              [1, 1, 0],
              [0, 1, 0],
              [0, 0, 0]
            ]
Output: 0

Example 2

Input: $M = [
              [0, 1,-2, 0, 1],
              [0, 0, 0, 1, 3],
              [0, 0, 0, 0, 0],
              [0, 0, 0, 0, 0]
            ]
Output: 1

Example 3

Input: $M = [
              [1, 0, 0, 4],
              [0, 1, 0, 7],
              [0, 0, 1,-1]
            ]
Output: 1

Example 4

Input: $M = [
              [0, 1,-2, 0, 1],
              [0, 0, 0, 0, 0],
              [0, 0, 0, 1, 3],
              [0, 0, 0, 0, 0]
            ]
Output: 0

Example 5

Input: $M = [
              [0, 1, 0],
              [1, 0, 0],
              [0, 0, 0]
            ]
Output: 0

Example 6

Input: $M = [
              [4, 0, 0, 0],
              [0, 1, 0, 7],
              [0, 0, 1,-1]
            ]
Output: 0

Reduced Row Echelon in Raku

sub is-first-echelon (@mat) {
    my @leading;
    for 0..@mat.end -> $i {
        my @row = |@mat[$i];
        for 0..@row.end -> $j {
            next if @row[$j] == 0;
            if @row[$j] == 1 {
                @leading[$i] = $j;
                last;
            } else {
            }
        }
        @leading[$i] = Inf unless defined @leading[$i];
    }
    return False unless [<] grep { $_ < Inf }, @leading; # rules 2 and 3
    return False unless [<=] @leading; 
    for 0..@leading.end -> $i {
        last if @leading[$i] == Inf;
        next unless defined @leading[$i];
        for 0..@mat.end -> $k {
            next if $i == @leading[$k];
            return False if @mat[$k][$i] != 0;
        }
    }
    return True;
}

my @tests = 
    [ [1,0,0,1], [0,1,0,2], [0,0,1,3]],
    [ [1, 1, 0], [0, 1, 0], [0, 0, 0]],
    [ [0, 1,-2, 0, 1], [0, 0, 0, 1, 3], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]],
    [ [1, 0, 0, 4], [0, 1, 0, 7], [0, 0, 1,-1]],
    [ [0, 1,-2, 0, 1], [0, 0, 0, 0, 0], [0, 0, 0, 1, 3], [0, 0, 0, 0, 0]],
    [ [0, 1, 0], [1, 0, 0], [0, 0, 0]],
    [ [4, 0, 0, 0], [0, 1, 0, 7], [0, 0, 1,-1]];

for @tests -> @test {
    printf "%-20s => ", "@test[0] ...";
    say is-first-echelon @test;
}

This program displays the following output:

$ raku ./first-echelon.raku
1 0 0 1 ...          => True
1 1 0 ...            => False
0 1 -2 0 1 ...       => True
1 0 0 4 ...          => True
0 1 -2 0 1 ...       => False
0 1 0 ...            => False
4 0 0 0 ...          => False

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on March 3, 2024. And, please, also spread the word about the Perl Weekly Challenge if you can.