Exercise: Matrix Transposition

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

Transposing a square matrix is an extremely simple operation.

Let's see the most naive implementation, and then a bit more efficient implementation, both in terms of memory and running time.

So here's the naive approach...

First we make a copy of matrix and then perform the transposition of matrix 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:

function transpose(matrix) {
   var n = matrix.length;
   var copiedMatrix = [];

   for (var i = 0; i < n; i++) {
      copiedMatrix.push([]);
      for (var j = 0; j < n; j++) {
         copiedMatrix[i].push(matrix[i][j]);
      }
   }

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

   return matrix;
}

Let's test it:

transpose([[1, 4], [10, 2]])

[[1, 10], [4, 2]]

transpose([[3, 5, 6], [10, 4, 2], [1, 7, 8]])

[[3, 10, 1], [5, 4, 7], [6, 2, 8]]

transpose([[2]])

[[2]]

Just as expected — it works absolutely correctly!

Although the approach shown above is absolutely fine and gives the correct answer, it is merely repeating over stuff.

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:

function transpose(matrix) {
   var n = matrix.length;
   var temp;

   for (var i = 0; i < n - 1; i++) {
      for (var 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:

transpose([[1, 4], [10, 2]])

[[1, 10], [4, 2]]

transpose([[3, 5, 6], [10, 4, 2], [1, 7, 8]])

[[3, 10, 1], [5, 4, 7], [6, 2, 8]]

transpose([[2]])

[[2]]

Yup, it works just as desired.