Objective
Transpose a given square matrix.
Difficulty
Description
In the world of matrices, yet another useful operation is that of transposition.
Let's see what exactly is it...
Matrix transposition, as the name suggests, is to exchange the positions of elements such that the ::i^{th}:: row becomes the ::i^{th}:: column 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:
then its tranpose ::\text{A}^{\text{t}}:: would be the following:
Similarly, if the matrix ::\text{A}:: is as follows:
then its tranpose ::\text{A}^{\text{t}}:: would be the following:
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:
function transpose(matrix) {
// your code
}Note that the function must mutate the original array.
Shown below is how the function transpose() should behave in a couple of cases:
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]]New file
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.
Solution
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!
A more efficient approach
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.
