Consider the 2D DFT:

where, as defined before

We further define

and rewrite the 2D transform as

The above two equations are the two steps for a 2D transform:

**Column Transform:**First consider the expression for . As the summation is with respect to the row index of , the column index can be treated as a parameter, and the expression is the 1D Fourier transform of the nth column vector of , which can be written in column vector (vertical) form for the nth column:

or more concisely

i.e., the nth column of is the 1D FT of the nth column of . Putting all columns together, we have

or more concisely

where is a by Fourier transform matrix.**Row Transform:**Now we reconsider the 2DFT expression above

As the summation is with respective to the column index n of , the row index can be treated as a parameter, and the expression is the 1D Fourier transform of the kth row vector of , which can be written in row vector (horizontal) form for the kth row:

or more concisely

i.e., the kth row of is the 1D FT of the kth row of . Putting all rows together, we have

or more concisely

But as , we finally have

Similarly, the inverse 2D DFT can be written as

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