Matrix Transpose

Linear Algebra

Easy

Problem

Theory

The transpose of a matrix flips it over its diagonal. Every element at position (i, j) moves to position (j, i). Rows become columns and columns become rows.

If A is an n \times m matrix, then A^T is an m \times n matrix defined by:

(A^T)_{ij} = A_{ji}

This simple operation appears everywhere in linear algebra, statistics, and machine learning. Understanding it deeply pays off.

A Concrete Example

Consider the matrix:

A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix}

This is a 2 \times 3 matrix (2 rows, 3 columns).

Its transpose is:

A^T = \begin{bmatrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \end{bmatrix}

This is a 3 \times 2 matrix (3 rows, 2 columns).

Notice what happened:

• Row 1 of A became column 1 of $$
• Row 2 of A became column 2 of $$
• The element at position (1, 2) in A (which is 2) is now at position (2, 1) in $$

The Transpose of a Vector

Vectors are special cases:

Column vector (shape n \times 1):

v = \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}

Its transpose is a row vector (shape 1 \times n):

v^T = \begin{bmatrix} 1 & 2 & 3 \end{bmatrix}

This is why you often see notation like x^T y for the dot product: it is a row vector times a column vector, which gives a scalar.

Key Properties of the Transpose

Double transpose returns the original:

(A^T)^T = A

Transpose of a sum:

(A + B)^T = A^T + B^T

Transpose of a product (order reverses!):

(AB)^T = B^T A^T

This reversal is crucial. If you have a chain of matrices, transposing reverses the order:

(ABC)^T = C^T B^T A^T

Transpose of a scalar multiple:

(cA)^T = c A^T

Special Matrices and Transpose

Symmetric matrices:

A matrix is symmetric if A^T = A. This means A_{ij} = A_{ji} for all entries. The matrix equals its mirror image across the diagonal.

Example:

\begin{bmatrix} 1 & 2 & 3 \\ 2 & 4 & 5 \\ 3 & 5 & 6 \end{bmatrix}

Symmetric matrices appear constantly in ML:

• Covariance matrices are symmetric
• Gram matrices (X^T X) are symmetric
• Distance matrices are symmetric

Skew-symmetric matrices:

A matrix is skew-symmetric if A^T = -A. The diagonal must be zero.

Example:

\begin{bmatrix} 0 & 2 & -3 \\ -2 & 0 & 5 \\ 3 & -5 & 0 \end{bmatrix}

Why Transpose Matters in Machine Learning

The Gram matrix X^T X:

If X is your data matrix with n samples and d features (shape n \times d), then:

• X^T X is a d \times d matrix
• Entry (i, j) is the dot product of feature column i with feature column j
• The diagonal contains the squared norms of each feature
• This matrix appears in linear regression, PCA, and many other algorithms

The covariance structure:

The sample covariance matrix is proportional to X^T X (after centering). Understanding how transposes work is essential for deriving the normal equations, PCA, and more.

Backpropagation:

In neural networks, the gradient with respect to the input of a linear layer involves the transpose of the weight matrix. If the forward pass is y = Wx, the backward pass involves W^T.

Transpose and Inner Products

The dot product of two vectors can be written as:

x \cdot y = x^T y = \sum_i x_i y_i

This is a 1 \times n row vector times an n \times 1 column vector, giving a 1 \times 1 scalar.

The outer product is the transpose arrangement:

x y^T

This is an n \times 1 column vector times a 1 \times m row vector, giving an n \times m matrix. Each entry is x_i y_j.

Implementation Perspective

Transposing a matrix in code is straightforward but has performance implications:

In-place vs. copy:

• For square matrices, you can swap elements across the diagonal in-place
• For non-square matrices, you must create a new matrix with swapped dimensions

Memory layout:

• Row-major storage (C, NumPy default): elements of each row are contiguous
• Transposing changes the access pattern
• What was row-major becomes column-major in the transpose

View vs. copy in NumPy:

• NumPy's .T returns a view (no data copy), just changes how indices map to memory
• This is very efficient but can cause subtle bugs if you modify the view

Examples

Hints

1. Create an output array whose row and column counts are reversed.
2. Inside nested loops, assign output[j, i] from A[i][j].

Requirements

• Return a new NumPy array of shape (M, N)
• Must not modify the original matrix
• Must work for non-square, rectangular matrices
• Do not use .T or np.transpose()
• Use manual indexing with loops or array operations

Constraints

• 1 ≤ N, M ≤ 1000
• Matrix elements can be any float or int
• Time limit: 200ms

Starter Code

import numpy as np

def matrix_transpose(A: list) -> np.ndarray:
    """
    Returns the transposed matrix as a NumPy array.
    """
    # Write code here
    pass

Test Cases