## Objective

Transpose a given square matrix.

## 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-33-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

*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.*

`matrix`

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.*