Free Books
   Free Books    Mathematics of the DFT  

Matrices

A matrix is defined as a rectangular array of numbers, e.g.,

$\displaystyle \mathbf{A}= \left[\begin{array}{cc} a & b \\ [2pt] c & d \end{array}\right] $

which is a $ 2\times2$ (``two by two'') matrix. A general matrix may be $ M\times N$, where $ M$ is the number of rows, and $ N$ is the number of columns of the matrix. For example, the general $ 3\times 2$ matrix is

$\displaystyle \left[\begin{array}{cc} a & b \\ c & d \\ e & f \end{array}\right]. $

Either square brackets or large parentheses may be used to delimit the matrix. The $ (i,j)$th elementH.1 of a matrix $ \mathbf{A}$ may be denoted by $ \mathbf{A}[i,j]$, $ \mathbf{A}(i,j)$, or $ \mathbf{A}_{ij}$. For example, $ \mathbf{A}[1,2]=b$ in the above two examples. The rows and columns of matrices are normally numbered from $ 1$ instead of from 0; thus, $ 1\leq i \leq M$ and $ 1\leq j \leq N$. When $ N=M$, the matrix is said to be square. The transpose of a real matrix $ \mathbf{A}\in{\bf R}^{M\times N}$ is denoted by $ \mathbf{A}^{\!\hbox{\tiny T}}$ and is defined by

$\displaystyle \mathbf{A}^{\!\hbox{\tiny T}}[i,j] \isdef \mathbf{A}[j,i]. $

While $ \mathbf{A}$ is $ M\times N$, its transpose is $ N\times M$. We may say that the ``rows and columns are interchanged'' by the transpose operation, and transposition can be visualized as ``flipping'' the matrix about its main diagonal. For example,

$\displaystyle \left[\begin{array}{cc} a & b \\ c & d \\ e & f \end{array}\right... ...\tiny T}} =\left[\begin{array}{ccc} a & c & e \\ b & d & f \end{array}\right]. $

A complex matrix $ \mathbf{A}\in{\bf C}^{M\times N}$, is simply a matrix containing complex numbers. The transpose of a complex matrix is normally defined to include conjugation. The conjugating transpose operation is called the Hermitian transpose. To avoid confusion, in this tutorial, $ \mathbf{A}^{\!\hbox{\tiny T}}$ and the word ``transpose'' will always denote transposition without conjugation, while conjugating transposition will be denoted by $ A^{\ast }$ and be called the ``Hermitian transpose'' or the ``conjugate transpose.'' Thus,

$\displaystyle A^{\ast }[i,j] \isdef \overline{\mathbf{A}[j,i]}. $

Matrix Multiplication

Let $ \mathbf{A}^{\!\hbox{\tiny T}}$ be a general $ M\times L$ matrix and let $ \mathbf{B}$ denote a general $ L\times N$ matrix. Denote the matrix product by $ \mathbf{C}=\mathbf{A}^{\!\hbox{\tiny T}}\, \mathbf{B}$. Then matrix multiplication is carried out by computing the inner product of every row of $ \mathbf{A}^{\!\hbox{\tiny T}}$ with every column of $ \mathbf{B}$. Let the $ i$th row of $ \mathbf{A}^{\!\hbox{\tiny T}}$ be denoted by $ \underline{a}^{\hbox{\tiny T}}_i$, $ i=1, 2,\ldots,M$, and the $ j$th column of $ \mathbf{B}$ by $ \underline{b}_j$, $ j=1,2,\ldots,N$. Then the matrix product $ \mathbf{C}=\mathbf{A}^{\!\hbox{\tiny T}}\, \mathbf{B}$ is defined as

$\displaystyle \mathbf{C}= \mathbf{A}^{\!\hbox{\tiny T}}\, \mathbf{B}= \left[\be... ...cdots & <\underline{a}^{\hbox{\tiny T}}_M,\underline{b}_N> \end{array}\right]. $

This definition can be extended to complex matrices by using a definition of inner product which does not conjugate its second argument.H.2 Examples:

$\displaystyle \left[\begin{array}{cc} a & b \\ c & d \\ e & f \end{array}\right... ...gamma & c\beta+d\delta \\ e\alpha+f\gamma & e\beta+f\delta \end{array}\right] $

$\displaystyle \left[\begin{array}{cc} \alpha & \beta \\ \gamma & \delta \end{ar... ...ma a + \delta b & \gamma c + \delta d & \gamma e + \delta f \end{array}\right] $

$\displaystyle \left[\begin{array}{c} \alpha \\ \beta \end{array}\right] \cdot \... ...pha a & \alpha b & \alpha c \\ \beta a & \beta b & \beta c \end{array}\right] $

$\displaystyle \left[\begin{array}{ccc} a & b & c \end{array}\right] \cdot \left... ...} \alpha \\ \beta \\ \gamma \end{array}\right] = a \alpha + b \beta + c \gamma $

An $ M\times L$ matrix $ \mathbf{A}$ can be multiplied on the right by an $ L\times N$ matrix, where $ N$ is any positive integer. An $ L\times N$ matrix $ \mathbf{A}$ can be multiplied on the left by a $ M\times L$ matrix, where $ M$ is any positive integer. Thus, the number of columns in the matrix on the left must equal the number of rows in the matrix on the right. Matrix multiplication is non-commutative, in general. That is, normally $ \mathbf{A}\,\mathbf{B}\neq \mathbf{B}\,\mathbf{A}$ even when both products are defined (such as when the matrices are square.) The transpose of a matrix product is the product of the transposes in reverse order:

$\displaystyle (\mathbf{A}\mathbf{B})^{\hbox{\tiny T}} = \mathbf{B}^{\hbox{\tiny T}} \mathbf{A}^{\!\hbox{\tiny T}} $

The identity matrix is denoted by $ \mathbf{I}$ and is defined as

$\displaystyle \mathbf{I}\isdef \left[\begin{array}{ccccc} 1 & 0 & 0 & \cdots &... ...dots & \vdots & \cdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 \end{array}\right] $

Identity matrices are always square. The $ N\times N$ identity matrix $ \mathbf{I}$, sometimes denoted as $ \mathbf{I}_N$, satisfies $ \mathbf{A}\cdot \mathbf{I}_N =\mathbf{A}$ for every $ M\times N$ matrix $ \mathbf{A}$. Similarly, $ \mathbf{I}_M\cdot \mathbf{A}=\mathbf{A}$, for every $ M\times N$ matrix $ \mathbf{A}$. As a special case, a matrix $ \mathbf{A}^{\!\hbox{\tiny T}}$ times a vector $ \underline{x}$ produces a new vector $ \underline{y}= \mathbf{A}^{\!\hbox{\tiny T}}\underline{x}$ which consists of the inner product of every row of $ \mathbf{A}^{\!\hbox{\tiny T}}$ with $ \underline{x}$

$\displaystyle \mathbf{A}^{\!\hbox{\tiny T}}\underline{x}= \left[\begin{array}{c... ...vdots \\ <\underline{a}^{\hbox{\tiny T}}_M,\underline{x}> \end{array}\right]. $

A matrix $ \mathbf{A}^{\!\hbox{\tiny T}}$ times a vector $ \underline{x}$ defines a linear transformation of $ \underline{x}$. In fact, every linear function of a vector $ \underline{x}$ can be expressed as a matrix multiply. In particular, every linear filtering operation can be expressed as a matrix multiply applied to the input signal. As a special case, every linear, time-invariant (LTI) filtering operation can be expressed as a matrix multiply in which the matrix is Toeplitz, i.e., $ \mathbf{A}^{\!\hbox{\tiny T}}[i,j] = \mathbf{A}^{\!\hbox{\tiny T}}[i-j]$ (constant along diagonals). As a further special case, a row vector on the left may be multiplied by a column vector on the right to form a single inner product:

$\displaystyle \underline{y}^{\ast }{\underline{x}} = \langle \underline{x},\underline{y}\rangle % \ip brackets huge due to y-underbar $

Solving Linear Equations Using Matrices

Consider the linear system of equations
\begin{eqnarray*} a x_1 + b x_2 &=& c \\ d x_1 + e x_2 &=& f \end{eqnarray*}
in matrix form:

$\displaystyle \left[\begin{array}{cc} a & b \\ [2pt] d & e \end{array}\right] \... ..._2 \end{array}\right] = \left[\begin{array}{c} c \\ [2pt] f \end{array}\right] $

This can be written in higher level form as

$\displaystyle \mathbf{A}\underline{x}= \underline{b}, $

where $ \mathbf{A}$ denotes the two-by-two matrix above, and $ \underline{x}$ and $ \underline{b}$ denote the two-by-one vectors. The solution to this equation is then

$\displaystyle \underline{x}= \mathbf{A}^{-1}\underline{b}= \left[\begin{array}{... ...\end{array}\right]^{-1}\left[\begin{array}{c} c \\ [2pt] f \end{array}\right]. $

The general two-by-two matrix inverse is given by

$\displaystyle \left[\begin{array}{cc} a & b \\ [2pt] d & e \end{array}\right]^{... ...rac{1}{ae-bd}\left[\begin{array}{cc} e & -b \\ [2pt] -d & a \end{array}\right] $

and the inverse exists whenever $ ae-bd$ (which is called the determinant of the matrix $ \mathbf{A}$) is nonzero. For larger matrices, numerical algorithms are used to invert matrices, such as used by Matlab based on LINPACK [25]. An initial introduction to matrices and linear algebra can be found in [47].
Next Section:
Matlab/Octave Examples
Previous Section:
Number Systems for Digital Audio