Objective

Create a function to transpose a given square matrix.

Difficulty

Easy

Description

In the world of matrices, a particularly useful operation is that of transposition.

Matrix transposition, as the name suggests, is to exchange the positions of elements such that the ::i^{th}:: row of the original matrix becomes the ::i^{th}:: column of the transposed matrix and the ::j^{th}:: column becomes the ::j^{th}:: row.

The new matrix obtained after transposing a given matrix ::\text{A}:: is called the transpose of ::\text{A}::, and is denoted as ::\text{A}^{\text{t}}::.

For instance, if the matrix ::\text{A}:: is as follows:

::\begin{bmatrix} 1 & 4 \\ 10 & 2 \end{bmatrix}::

then its tranpose ::\text{A}^{\text{t}}:: would be the following:

::\begin{bmatrix} 1 & 10 \\ 4 & 2 \end{bmatrix}::

Similarly, if the matrix ::\text{A}:: is as follows:

::\begin{bmatrix} 3 & 5 & 6 \\ 10 & 4 & 2 \\ 1 & 7 & 8 \end{bmatrix}::

then its tranpose ::\text{A}^{\text{t}}:: would be the following:

::\begin{bmatrix} 3 & 10 & 1 \\ 5 & 4 & 7 \\ 6 & 2 & 8 \end{bmatrix}::

In this exercise, you have to create a function called transpose() that tranposes a given square matrix.

The matrix is provided as an argument to the function which then returns back its tranpose.

Note that the function MUST mutate the original array.

Shown below is how the function transpose() should behave in a couple of cases:

<?php

/* Functions defined here... */

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

New file

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.

Solution

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));
1 10 4 2 1 10 4 2

Just as expected, it works absolutely correctly!

A more efficient approach

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.

::\begin{bmatrix} 3 & \textcolor{white}{\colorbox{#001fcc} 5} & \textcolor{white}{\colorbox{#001fcc} 6} \\ 10 & 4 & \textcolor{white}{\colorbox{#001fcc} 2} \\ 1 & 7 & 8 \end{bmatrix}::

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);
1 10 4 2 1 10 4 2

Yup, it works just as desired.