And here's a WxH version

Excellent. And here a slope for you to slide, sort of in splendid isolation, from a plot fanatic:

sub sms_WxH_Perl_sliding_tybalt89 ( $m, $width, $height ) {
    my @new = zip_by { [ @_ ] } map [ nslide $height, @$_ ],
      zip_by { [ @_ ] } map [ nslide $width, @$_ ], @$m;
    return \@new
}

__END__

           Time (s) vs. N (NxN submatrix, 1500x1500 matrix)
      +-----------------------------------------------------------+
  1.8 |-+  +      +      +      +       +      +      +      +  +-|
      |    A                                                      |
      |    A                                                      |
  1.6 |-+                                                       +-|
      |        A                                                  |
      |                                                           |
  1.4 |-+                                                       +-|
      |           A                                               |
      |                                                           |
  1.2 |-+             A                                         +-|
      |                                                           |
      |                  A                                        |
      |                      A                                    |
    1 |-+                                                       +-|
      |                         A                                 |
      |                                                           |
  0.8 |-+                           A                           +-|
      |                                                           |
      |                                 A                         |
  0.6 |-+                                  A                    +-|
      |                                        A                  |
      |                                                           |
  0.4 |-+                                         A             +-|
      |                                               A           |
      |                                                  A        |
  0.2 |-+                                                       +-|
      |                                                      A    |
      |    +      +      +      +       +      +      +      +    |
    0 +-----------------------------------------------------------+
           0     200    400    600     800    1000   1200   1400
                 sms_WxH_Perl_sliding_tybalt89    A
  +------+-------+
  | N    | A     |
  +------+-------+
  | 2    | 1.700 |
  | 10   | 1.725 |
  | 100  | 1.538 |
  | 200  | 1.387 |
  | 300  | 1.259 |
  | 400  | 1.131 |
  | 500  | 1.016 |
  | 600  | 0.894 |
  | 700  | 0.784 |
  | 800  | 0.678 |
  | 900  | 0.578 |
  | 1000 | 0.484 |
  | 1100 | 0.394 |
  | 1200 | 0.309 |
  | 1300 | 0.231 |
  | 1400 | 0.153 |
  +------+-------+
[download]