Using code stolen from Re: Alpha number sort (one, true, natural sort). Like the grep/sort/grep code you have, it replaces each number with a fixed-length number-like thing that regular cmp will sort properly (the magic is in s[(\d+)][ pack "N", $1 ]ge).

my @sorted_matrix = sort { natural_cmp($a->[0], $b->[0]) } @matrix;

for my $i ( 0 .. $#sorted_matrix ) {
    for my $j ( 0 .. $#{ $sorted_matrix[$i] } ) {
        print "$i $j -> $sorted_matrix[$i][$j]\n";
    }
    print "\n";
}


=head3 natural_cmp

A fast, flexible, stable comparator that sorts strings naturally (that
+ is,
numerical substrings are compared as numbers).

Code lifted from tye on perlmonks: http://www.perlmonks.org/?node_id=4
+42285

Limitations: http://www.perlmonks.org/?node_id=483466

  It doesn't "properly" sort negative numbers, non-fixed decimal value
+s,
  nor integers larger than 2^32-1.

=cut

sub natural_cmp {
  my ($x,$y) = map { my $key = $_; $key =~ s[(\d+)][ pack "N", $1 ]ge;
+ $key } @_;
  $x cmp $y;
}
[download]

Which gives (showing just the sorting column):

0 0 -> A1a1
1 0 -> A1a12
2 0 -> A10a1
3 0 -> A12a1
[download]