I would also use a sort block but keeping your starting point and required output structure intact and after your second post it looks like this:

my @result=();
for (my $i=0; $i<=$#matrix;$i++){
    my @resline = ( $i+1 );
    my @keys = ();
    for my $k ( sort { $matrix[$i]{$b} <=> $matrix[$i]{$a} } keys %{ $
+matrix[$i] } ) {
        push @keys, $k;
        push @resline, $matrix[$i]{$k};
    }
    push @resline, @keys;
    push @result, \@resline; # nb. pushing the reference not the array
+ this time
}
[download]