3.8.1: Discrete Linear Transformations

In general, a discrete linear transformation takes a vector as input and returns another vector of the same size. The elements of the output vector are a linear combination of the elements of the input vector, and therefore this transformation can be carried out by matrix multiplication.

For example, consider the following matrix multiplication:

\begin{equation} \tag{3.1}
\left[\begin{array}{cc}
1 & 1 \\
1 & -1
\end{array}\right]\left[\begin{array}{l}
4 \\
1
\end{array}\right] \rightarrow\left[\begin{array}{l}
5 \\
3
\end{array}\right] .
\end{equation}

If the vectors and matrices in this equation are named

then Equation 3.1 becomes

O = \(\mathbb{C}\)I. \(\tag{3.2}\)

We can now think of \(\mathbb{C}\) as a discrete linear transformation that transforms the input vector I into the output vector O. Incidentally, this particular transformation \(\mathbb{C}\) is one that transforms the input vector I into a vector that contains the sum (5) and the difference (3) of its components.\(^3\)

The procedure is the same for a 3×3 matrix acting on a 3 element vector:

\[ \tag{3.3} \begin{bmatrix} c_{1,1} & c_{1,2} & c_{1,3} \\ c_{2,1} & c_{2,2} & c_{2,3} \\ c_{3,1} & c_{3,2} & c_{3,3} \end{bmatrix} \begin{bmatrix} i_1 \\ i_2 \\ i_3 \end{bmatrix} \longrightarrow \begin{array}{lcl} o_1 & = & \sum_{j} c_{1,j}i_j \\ o_2 & = & \sum_{j} c_{2,j}i_j \\ o_3 & = & \sum_{j} c_{3,j}i_j \end{array} \]

which again can be written in the succinct form

O = \(\mathbb{C}\)I. \(\tag{3.4}\)

where now the vectors are of size 3 and the matrix is 3×3.

In general, for a transformation of this form, if the matrix \(\mathbb{C}\) has an inverse \(mathbb{C}^{−1}\) then the vector I can be reconstructed from its transform by

I = \(\mathbb{C}^{-1}\)O. \(\tag{3.5}\)

Equations 3.3 and 3.1 illustrate the linear transformation when the input is a column vector. The procedure for a row-vector is similar, but the order of the vector and matrix is reversed, and the transformation matrix is transposed.\(^4\) This change is consistent with viewing a row vector as the transpose of the column vector. For example:

Vectors are useful for dealing with objects that have a one-dimensional character, such as a sound waveform sampled a finite number of times. Images are inherently two-dimensional in nature, and it is natural to use matrices to represent the properties of the pixels of an image. Video is inherently three-dimensional (two space and one time) and it is natural to use three-dimensional arrays of numbers to represent their data. The succinct vector-matrix notation given here extends gracefully to two-dimensional systems, but not to higher dimensions (other mathematical notations can be used).

Extending linear transformations to act on matrices, not just vectors, is not difficult. For example, consider a very small image of six pixels, three rows of two pixels each, or two columns of three pixels each. A number representing some property of each pixel (such as its brightness on a scale of 0 to 1) could form a 3×2 matrix:

\[ \tag{3.7} \begin{bmatrix} i_{1,1} & i_{1,2} \\ i_{2,1} & i_{2,2} \\ i_{3,1} & i_{3,2} \end{bmatrix} \]

The most general linear transformation that leads to a 3×2 output matrix would require 36 coefficients. When the arrangement of the elements in a matrix reflects the underlying object being represented, a less general set of linear transformations, that operate on the rows and columns separately, using different matrices \(\mathbb{C}\) and \(\mathbb{D}\), may be useful:

\[ \tag{3.8} \begin{bmatrix} c_{1,1} & c_{1,2} & c_{1,3} \\ c_{2,1} & c_{2,2} & c_{2,3} \\ c_{3,1} & c_{3,2} & c_{3,3} \end{bmatrix} \begin{bmatrix} i_{1,1} & i_{1,2} \\ i_{2,1} & i_{2,2} \\ i_{3,1} & i_{3,2} \end{bmatrix} \begin{bmatrix} d_{1,1} & d_{1,2} \\ d_{2,1} & d_{2,2} \end{bmatrix} \longrightarrow \begin{bmatrix} o_{1,1} & o_{1,2} \\ o_{2,1} & o_{2,2} \\ o_{3,1} & o_{3,2} \end{bmatrix} \]

or, in matrix notation,

\(\mathbb{O} = \mathbb{C}\mathbb{I}\mathbb{D}, \tag{3.9}\)

Note that the matrices at left \(\mathbb{C}\) and right \(\mathbb{D}\) in this case are generally of different size, and may or may not be of the same general character. (An important special case is when \(\mathbb{I}\) is square, i.e., it contains the same number of rows and columns. In this case the output matrix \(\mathbb{O}\) is also square, and \(\mathbb{C}\) and \(\mathbb{D}\) are the same size.)

---

\(^3\)It happens that \(\mathbb{C}\) is √2 times the 2×2 Discrete Cosine Transformation matrix defined in Section 3.8.2.

\(^4\)Transposing a matrix means flipping its elements about the main diagonal, so the \(i, j\) element of the transpose is the \(j, i\) element of the original matrix. Transposed matrices are denoted with a superscript \(T\), as in \(\mathbb{C}^T\). In general the transpose of a product of two matrices (or vectors) is the product of the two transposed matrices or vectors, in reverse order: \((\mathbb{AB})^T\) = \(\mathbb{B}^T\mathbb{A}^T\).