Consider the 2-D DFT of an signal
(
):

where we have defined

where . Note that the dimension of the spectrum is also .

As the summation above is with respect to the row index while the column
index can be treated as a parameter, this expression can be considered
as a one-dimensional Fourier transform of the nth column of the
2-D signal matrix
, which can be
written in column vector (vertical) form as:

where is a Fourier transform matrix. Putting all these columns together, we can write

We also note that the summation in the expression for is with respective
to the column index of while the row index number can be treated
as a parameter, the expression is one-dimensional Fourier transform of the kth row
of , which can be written in row vector (horizontal) form as

where is a Fourier transform matrix. Putting all these rows together, we can write

or more concisely

But since , we have

This transform expression indicates that 2D DFT can be implemented by transforming all the rows of and then transforming all the columns of the resulting matrix . The order of the row and column transforms is not important.

Similarly, the inverse 2D DFT can be written as

Again note that is a symmetric unitary matrix:

It is obvious that the complexity of 2D DFT is which can be reduced to if FFT is used.