Exercise: Matrix Transposition

Inside the directory you created for this course on PHP, create a new folder called Exercise-23-Matrix-Transposition and put the .php solution files for this exercise within it.

Transposing a square matrix is an extremely simple operation.

Let's first see the most naive implementation and then consider a slightly more efficient implementation.

To start with, here's the minimal definition of transpose():

<?php

function &transpose(&$matrix) {
   // Code to go here.
}

By this point, it's quite obvious as to why we use & in &$matrix and &transpose — because we need to mutate the original matrix and even return that original matrix, respectively.

So here's the naive approach...

First we make a copy of $matrix, store it in $matrix_copy, and then perform the transposition with the help of this copy. The actual transposition operation is quite straightforward — the ::(i, j)^{th}:: element of $matrix is set to the ::(j, i)^{th}:: element of its copy.

That's it.

Shown below is the code accomplishing this:

<?php

function &transpose(&$matrix) {
   $n = count($matrix);
   $matrix_copy = $matrix;

   for ($i = 0; $i < $n; $i++) {
      for ($j = 0; $j < $n; $j++) {
         $matrix[$i][$j] = $matrix_copy[$j][$i];
      }
   }
   return $matrix;
}

Let's test it:

<?php

/* Functions defined here... */

function &transpose(&$matrix) { /* ... */ }

$a = [ [1, 4], [10, 2] ];
print_matrix(transpose($a));
echo "\n";
print_matrix(transpose($a));

Just as expected, it works absolutely correctly!

Although the approach shown above is absolutely fine and gives the correct answer, there's technically no need to make a copy of the given matrix.

If you notice it carefully, the transpose of a square matrix is simply a matter of reflecting elements amid the main diagonal (i.e. the diagonal that runs from the top-left corner to the bottom-right corner). That is, corresponding elements on either side of this diagonal are swapped with one another.

Shown below is a simple illustration for this.

Only the highlighted elements here need to be considered in the swapping. The elements occuring on the diagonal remain in their original positions so we don't need to consider them. The elements below the diagonal will anyways be considered when swapping the elements above the diagonal.

So, in short, is we just swap the highlighted elements here with the corresponding elements below the diagonal, we'd have transposed our original matrix.

Now the question is that how do we iterate over the highlighted elements shown here, or the elements above the main diagonal of any arbitrary square matrix.

Well, if you see it closely in the illustration above, we iterate over ::n - 1:: rows, leaving off the last row. Then for each ::i^{th}:: row, we start off with the ::(i + 1)^{th}:: element in that row and go upto the end of the row.

And that's it.

Let's convert this into code:

<?php

function &transpose(&$matrix) {
   $n = count($matrix);

   for ($i = 0; $i < $n - 1; $i++) {
      for ($j = $i + 1; $j < $n; $j++) {
         $temp = $matrix[$i][$j];
         $matrix[$i][$j] = $matrix[$j][$i];
         $matrix[$j][$i] = $temp;
      }
   }
   return $matrix;
}

As you can see, in this implementation, we didn't have to copy the matrix, nor iterate over it entirely in order to transpose each element — just swapping the elements above the diagonal solves the problem.

It's now time to test this implementation:

<?php

/* Functions defined here... */

function &transpose(&$matrix) { /* ... */ }

$a = [ [1, 4], [10, 2] ];
print_matrix(transpose($a));
echo "\n";
print_matrix($a);

Yup, it works just as desired.