Perhaps I'm missing something, but does the output below using the code changes do what you need?

my @sorted_matrix;

{
    no warnings 'numeric';
    @sorted_matrix = sort {$a->[0] <=> $b->[0]} @matrix;
}

__END__
0 0 -> A1a1
0 1 -> img1
0 2 -> x123
0 3 -> y123

1 0 -> A1a12
1 1 -> img3
1 2 -> x456
1 3 -> y789

2 0 -> A10a1
2 1 -> img4
2 2 -> x456
2 3 -> y123

3 0 -> A12a1
3 1 -> img5
3 2 -> x456
3 3 -> y456
[download]