---
title: "FourierMatrix"
language: "en"
type: "Symbol"
summary: "FourierMatrix[n] returns an n*n Fourier matrix."
keywords: 
- Fourier matrix
- dft
- discrete Fourier transform
- Fourier
canonical_url: "https://reference.wolfram.com/language/ref/FourierMatrix.html"
source: "Wolfram Language Documentation"
related_guides: 
  - 
    title: "Structured Arrays"
    link: "https://reference.wolfram.com/language/guide/StructuredArrays.en.md"
  - 
    title: "Summation Transforms"
    link: "https://reference.wolfram.com/language/guide/SummationTransforms.en.md"
related_functions: 
  - 
    title: "FourierDCTMatrix"
    link: "https://reference.wolfram.com/language/ref/FourierDCTMatrix.en.md"
  - 
    title: "FourierDSTMatrix"
    link: "https://reference.wolfram.com/language/ref/FourierDSTMatrix.en.md"
  - 
    title: "Fourier"
    link: "https://reference.wolfram.com/language/ref/Fourier.en.md"
  - 
    title: "InverseFourier"
    link: "https://reference.wolfram.com/language/ref/InverseFourier.en.md"
  - 
    title: "HadamardMatrix"
    link: "https://reference.wolfram.com/language/ref/HadamardMatrix.en.md"
  - 
    title: "VandermondeMatrix"
    link: "https://reference.wolfram.com/language/ref/VandermondeMatrix.en.md"
---
# FourierMatrix

FourierMatrix[n] returns an n×n Fourier matrix.

## Details and Options

* ``FourierMatrix`` of order ``n`` returns a list of the length-``n`` discrete Fourier transform's basis sequences.

* Each entry of the Fourier matrix is by default defined as $F[[r,s]]=\frac{1}{\sqrt{\text{\textit{$n$}}}}\omega ^{(\text{\textit{$r$}}-1)(\text{\textit{$s$}}-1)}$, where $\omega =e^{2\pi  \text{\textit{$i$}}\text{\textit{$ $}}/\text{\textit{$n$}}}$.

[image]

* Rows of the ``FourierMatrix`` are basis sequences of the discrete Fourier transform.

* The result ``F`` of ``FourierMatrix[n]`` is complex symmetric and unitary, meaning that ``F^-1`` is ``Conjugate[F]``.

* The following options can be given:

|                    |           |                                            |
| ------------------ | --------- | ------------------------------------------ |
| FourierParameters  | {0, 1}    | parameters to define the Fourier transform |
| TargetStructure    | Automatic | the structure of the returned matrix       |
| WorkingPrecision   | Infinity  | precision at which to create entries       |

* Different choices of definitions for the Fourier matrix can be specified using the option ``FourierParameters``. With the setting ``FourierParameters -> {a, b}``, the Fourier matrix has entries defined as $F[[r,s]]=\frac{1}{\text{\textit{$n$}}^{(1-\text{\textit{$a$}})/2}}\omega ^{b(\text{\textit{$r$}}-1)(\text{\textit{$s$}}-1)}$, where $\omega =e^{2\pi  \text{\textit{$i$}}\text{\textit{$ $}}/\text{\textit{$n$}}}$.

[image]

* Some common choices for ``{a, b}`` are ``{0, 1}`` (physics), ``{-1, 1}`` (data analysis), ``{1, -1}`` (signal processing).

* Possible settings for ``TargetStructure`` include:

|              |                                                  |
| ------------ | ------------------------------------------------ |
| Automatic    | automatically choose the representation returned |
| "Dense"      | represent the matrix as a dense matrix           |
| "Structured" | represent the matrix as a structured array       |
| "Symmetric"  | represent the matrix as a symmetric matrix       |
| "Unitary"    | represent the matrix as a unitary matrix         |

* With ``FourierMatrix[…, TargetStructure -> Automatic]``, a dense matrix is returned if the number of matrix entries is less than a preset threshold, and a structured array is returned otherwise.

* The result of ``FourierMatrix[n].list`` is equivalent to ``Fourier[list]`` when ``list`` has length ``n``. However, the computation of ``Fourier[list]`` is much faster and has less numerical error, unless ``FourierMatrix`` is kept as a structured array. »

* For a structured ``FourierMatrix`` ``sa``, the following properties ``"prop"`` can be accessed as ``sa["prop"]`` :

|                        |                                                                 |
| ---------------------- | --------------------------------------------------------------- |
| "FourierParameters"    | parameters {a, b}                                               |
| "WorkingPrecision"     | precision used internally                                       |
| "Properties"           | list of supported properties                                    |
| "Structure"            | type of structured array                                        |
| "StructuredData"       | internal data stored by the structured array                    |
| "StructuredAlgorithms" | list of functions with special methods for the structured array |
| "Summary"              | summary information, represented as a Dataset                   |

---

## Examples (12)

### Basic Examples (2)

A $4\times 4$ Fourier matrix:

```wl
In[1]:= FourierMatrix[4]//MatrixForm

Out[1]//MatrixForm=
(⁠|       |        |        |        |
| ----- | ------ | ------ | ------ |
| (1/2) | (1/2)  | (1/2)  | (1/2)  |
| (1/2) | (I/2)  | -(1/2) | -(I/2) |
| (1/2) | -(1/2) | (1/2)  | -(1/2) |
| (1/2) | -(I/2) | -(1/2) | (I/2)  |⁠)
```

---

A large Fourier matrix:

```wl
In[1]:= FourierMatrix[800]

Out[1]= FourierMatrix[StructuredArray`StructuredData[{800, 800}, {{0, 1}, Infinity}]]
```

### Scope (2)

The real and imaginary parts of the Fourier's basis sequences of length 128:

```wl
In[1]:=
f = FourierMatrix[128];
{ArrayPlot[Re[f]], ArrayPlot[Im[f]]}

Out[1]= {[image], [image]}
```

---

Construct a structured Fourier matrix using the option setting ``TargetStructure -> "Structured"`` :

```wl
In[1]:= ℱ = FourierMatrix[512, TargetStructure -> "Structured"]

Out[1]= FourierMatrix[StructuredArray`StructuredData[{512, 512}, {{0, 1}, Infinity}]]
```

The structured representation saves a significant amount of memory for larger matrices:

```wl
In[2]:= {ByteCount[ℱ], ByteCount[Normal[ℱ]]}

Out[2]= {488, 119943424}
```

### Options (3)

#### FourierParameters (1)

The default definition of the Fourier matrix:

```wl
In[1]:= FourierMatrix[4, FourierParameters -> {0, 1}]//MatrixForm

Out[1]//MatrixForm=
(⁠|       |        |        |        |
| ----- | ------ | ------ | ------ |
| (1/2) | (1/2)  | (1/2)  | (1/2)  |
| (1/2) | (I/2)  | -(1/2) | -(I/2) |
| (1/2) | -(1/2) | (1/2)  | -(1/2) |
| (1/2) | -(I/2) | -(1/2) | (I/2)  |⁠)
```

Use the definition of the Fourier matrix used in signal processing:

```wl
In[2]:= FourierMatrix[4, FourierParameters -> {1, -1}]//MatrixForm

Out[2]//MatrixForm=
(⁠|   |    |    |    |
| - | -- | -- | -- |
| 1 | 1  | 1  | 1  |
| 1 | -I | -1 | I  |
| 1 | -1 | 1  | -1 |
| 1 | I  | -1 | -I |⁠)
```

Use the definition of the Fourier matrix used in data analysis:

```wl
In[3]:= FourierMatrix[4, FourierParameters -> {-1, 1}]//MatrixForm

Out[3]//MatrixForm=
(⁠|       |        |        |        |
| ----- | ------ | ------ | ------ |
| (1/4) | (1/4)  | (1/4)  | (1/4)  |
| (1/4) | (I/4)  | -(1/4) | -(I/4) |
| (1/4) | -(1/4) | (1/4)  | -(1/4) |
| (1/4) | -(I/4) | -(1/4) | (I/4)  |⁠)
```

#### TargetStructure (1)

Return the Fourier matrix as a dense matrix:

```wl
In[1]:= FourierMatrix[4, TargetStructure -> "Dense"]

Out[1]= {{(1/2), (1/2), (1/2), (1/2)}, {(1/2), (I/2), -(1/2), -(I/2)}, {(1/2), -(1/2), (1/2), -(1/2)}, {(1/2), -(I/2), -(1/2), (I/2)}}
```

Return the Fourier matrix as a structured array:

```wl
In[2]:= FourierMatrix[4, TargetStructure -> "Structured"]

Out[2]= FourierMatrix[StructuredArray`StructuredData[{4, 4}, {{0, 1}, Infinity}]]
```

Return the Fourier matrix as a symmetric matrix:

```wl
In[3]:= FourierMatrix[4, TargetStructure -> "Symmetric"]

Out[3]=
SymmetricMatrix[StructuredArray`StructuredData[{4, 4}, 
  {{{Rational[1, 2], Rational[1, 2], Rational[1, 2], Rational[1, 2]}, 
    {Rational[1, 2], Complex[0, Rational[1, 2]], Rational[-1, 2], Complex[0, Rational[-1, 2]]}, 
    {Rational[1, 2], Rational[-1, 2], Rational[1, 2], Rational[-1, 2]}, 
    {Rational[1, 2], Complex[0, Rational[-1, 2]], Rational[-1, 2], Complex[0, Rational[1, 2]]}}, 
   0}]]
```

Return the Fourier matrix as a unitary matrix:

```wl
In[4]:= FourierMatrix[4, TargetStructure -> "Unitary"]

Out[4]=
UnitaryMatrix[StructuredArray`StructuredData[{4, 4}, 
  {{{Rational[1, 2], Rational[1, 2], Rational[1, 2], Rational[1, 2]}, 
    {Rational[1, 2], Complex[0, Rational[1, 2]], Rational[-1, 2], Complex[0, Rational[-1, 2]]}, 
    {Rational[1, 2], Rational[-1, 2], Rational[1, 2], Rational[-1, 2]}, 
    {Rational[1, 2], Complex[0, Rational[-1, 2]], Rational[-1, 2], Complex[0, Rational[1, 2]]}}, 
   0}]]
```

#### WorkingPrecision (1)

Use machine precision:

```wl
In[1]:= FourierMatrix[3, WorkingPrecision -> MachinePrecision]//MatrixForm

Out[1]//MatrixForm=
(⁠|                 |                   |                   |
| --------------- | ----------------- | ----------------- |
| 0.57735         | 0.57735           | 0.57735           |
| 0.57735  + 0. I | -0.288675 + 0.5 I | -0.288675 - 0.5 I |
| 0.57735  + 0. I | -0.288675 - 0.5 I | -0.288675 + 0.5 I |⁠)
```

Use arbitrary precision:

```wl
In[2]:= FourierMatrix[3, WorkingPrecision -> 20]//MatrixForm

Out[2]//MatrixForm=
(⁠|                       |                                                  |                                                  |
| --------------------- | ------------------------------------------------ | ----------------------------------------- ... 2691896257645 | -0.2886751345948128823 + 0.5000000000000000000 I | -0.2886751345948128823 - 0.5000000000000000000 I |
| 0.5773502691896257645 | -0.2886751345948128823 - 0.5000000000000000000 I | -0.2886751345948128823 + 0.5000000000000000000 I |⁠)
```

### Applications (3)

The efficiency of the fast Fourier transform (FFT) relies on being able to form a larger Fourier matrix from two smaller ones. Generate two small Fourier matrices of sizes ``p`` and ``q`` :

```wl
In[1]:=
p = 2;
MatrixForm[fmatp = FourierMatrix[p]]

Out[1]//MatrixForm=
(⁠|             |              |
| ----------- | ------------ |
| (1/Sqrt[2]) | (1/Sqrt[2])  |
| (1/Sqrt[2]) | -(1/Sqrt[2]) |⁠)

In[2]:=
q = 3;
MatrixForm[fmatq = FourierMatrix[q]]

Out[2]//MatrixForm=
(⁠|             |                        |                        |
| ----------- | ---------------------- | ---------------------- |
| (1/Sqrt[3]) | (1/Sqrt[3])            | (1/Sqrt[3])            |
| (1/Sqrt[3]) | (E^(2 I π/3)/Sqrt[3])  | (E^-(2 I π/3)/Sqrt[3]) |
| (1/Sqrt[3]) | (E^-(2 I π/3)/Sqrt[3]) | (E^(2 I π/3)/Sqrt[3])  |⁠)
```

The Fourier matrix of size ``p q`` can be expressed as a product of four simpler matrices:

```wl
In[3]:=
fpkp = KroneckerProduct[fmatp, IdentityMatrix[q]];
diag = DiagonalMatrix[Flatten[Table[Exp[(2 π I j k/p q)], {k, 0, p - 1}, {j, 0, q - 1}]]];
fqkp = BlockDiagonalMatrix[ConstantArray[fmatq, p]];
shuffle = PermutationMatrix[Flatten[Partition[Range[p q], p], {{2, 1}}]];
MatrixForm[fmatpq = fpkp.diag.fqkp.shuffle]

Out[3]//MatrixForm=
(⁠|             |                        |                        |              |                        |                         |
| ----------- | ---------------------- | ---------------------- | ------------ | ---------------------- | -------- ... E^(I π/3)/Sqrt[6])   | (E^(2 I π/3)/Sqrt[6])  | (1/Sqrt[6])  | (E^-(2 I π/3)/Sqrt[6]) | -(E^-(I π/3)/Sqrt[6])   |
| (1/Sqrt[6]) | -(E^(2 I π/3)/Sqrt[6]) | (E^-(2 I π/3)/Sqrt[6]) | -(1/Sqrt[6]) | (E^(2 I π/3)/Sqrt[6])  | -(E^-(2 I π/3)/Sqrt[6]) |⁠)
```

Show that the resulting matrix is equivalent to the result of ``FourierMatrix`` :

```wl
In[4]:= fmatpq == FourierMatrix[p q]

Out[4]= True
```

The discrete Fourier transform of a vector can be computed by successively multiplying the factors of the Fourier matrix to the vector:

```wl
In[5]:=
data = RandomComplex[1 + I, p q];
res = fpkp.(diag.(fqkp.(shuffle.data)))

Out[5]= {1.1255  + 1.55891 I, 0.051134  - 0.0608032 I, 0.329471  + 0.0465458 I, -0.710853 - 0.0320981 I, 0.0339912  - 0.22356 I, -0.0203209 - 0.289852 I}
```

The result is equivalent to applying ``Fourier`` to the vector:

```wl
In[6]:= Chop[Max[Abs[res - Fourier[data]]]] == 0

Out[6]= True
```

---

Define a function for constructing a circulant matrix from a vector:

```wl
In[1]:= circulant[v_] := ToeplitzMatrix[v, RotateRight[Reverse[v]]]

In[2]:= circulant[Array[C, 4]]//MatrixForm

Out[2]//MatrixForm=
(⁠|      |      |      |      |
| ---- | ---- | ---- | ---- |
| C[1] | C[4] | C[3] | C[2] |
| C[2] | C[1] | C[4] | C[3] |
| C[3] | C[2] | C[1] | C[4] |
| C[4] | C[3] | C[2] | C[1] |⁠)
```

Circulant matrices can be diagonalized by the Fourier matrix:

```wl
In[3]:=
fm = FourierMatrix[4];
ConjugateTranspose[fm].circulant[Array[C, 4]].fm//FullSimplify//MatrixForm

Out[3]//MatrixForm=
(⁠|                           |                               |                           |                                 |
| ------------------------- | ----------------------------- | ------------------------- | -------------------------------  ... 0                         | 0                             | C[1] - C[2] + C[3] - C[4] | 0                               |
| 0                         | 0                             | 0                         | C[1] + I (C[2] + I C[3] - C[4]) |⁠)
```

The diagonal elements of the resulting diagonal matrix are the same as the product of the Fourier matrix and the starting vector, up to a constant scaling factor:

```wl
In[4]:= Sqrt[4]Conjugate[fm].Array[C, 4]//FullSimplify

Out[4]= {C[1] + C[2] + C[3] + C[4], C[1] - I C[2] - C[3] + I C[4], C[1] - C[2] + C[3] - C[4], C[1] + I (C[2] + I C[3] - C[4])}
```

---

A Fourier matrix with unit normalization:

```wl
In[1]:= fmat[n_Integer] := FourierMatrix[n, FourierParameters -> {1, 1}]
```

For even dimensions, the permanent of the matrix is zero:

```wl
In[2]:= Table[Permanent[fmat[n]]//Simplify, {n, 2, 10, 2}]

Out[2]= {0, 0, 0, 0, 0}
```

For odd dimensions, the permanent of the matrix is always an integer:

```wl
In[3]:= Table[Permanent[fmat[n]]//RootReduce, {n, 3, 11, 2}]

Out[3]= {-3, -5, -105, 81, 6765}
```

For an odd prime ``p > 3``, the permanent of the ``p``×``p`` matrix is congruent to ``p!``, modulo ``p^3`` :

```wl
In[4]:= With[{p = 13}, Mod[{RootReduce[Permanent[fmat[p]]], p!}, p^3]]

Out[4]= {2184, 2184}
```

### Properties & Relations (2)

``FourierMatrix`` can be represented as a scaled ``VandermondeMatrix`` :

```wl
In[1]:=
{n, a, b} = {16, 1, -1};
fm = FourierMatrix[n, FourierParameters -> {a, b}];
fm == (1/n^(1 - a) / 2)VandermondeMatrix[Exp[(2π I b/n) Range[0, n - 1]]]

Out[1]= True
```

---

The Fourier transform of a vector is equivalent to the vector multiplied by a Fourier matrix:

```wl
In[1]:=
data = RandomReal[1, 6];
FourierMatrix[6] . data  == Fourier[data]

Out[1]= True
```

The inverse Fourier transform is equivalent to multiplying by the conjugate transpose:

```wl
In[2]:= ConjugateTranspose[FourierMatrix[6]]. data  == InverseFourier[data]

Out[2]= True
```

``Fourier`` is much faster than the matrix-based computation:

```wl
In[3]:=
data = RandomReal[1, 1024];
{AbsoluteTiming[Do[Fourier[data], {10}];], 
	AbsoluteTiming[fm = FourierMatrix[1024, WorkingPrecision -> MachinePrecision];Do[fm.data, {10}];]}

Out[3]= {{0.0053491, Null}, {9.64713, Null}}
```

## See Also

* [`FourierDCTMatrix`](https://reference.wolfram.com/language/ref/FourierDCTMatrix.en.md)
* [`FourierDSTMatrix`](https://reference.wolfram.com/language/ref/FourierDSTMatrix.en.md)
* [`Fourier`](https://reference.wolfram.com/language/ref/Fourier.en.md)
* [`InverseFourier`](https://reference.wolfram.com/language/ref/InverseFourier.en.md)
* [`HadamardMatrix`](https://reference.wolfram.com/language/ref/HadamardMatrix.en.md)
* [`VandermondeMatrix`](https://reference.wolfram.com/language/ref/VandermondeMatrix.en.md)

## Related Guides

* [Structured Arrays](https://reference.wolfram.com/language/guide/StructuredArrays.en.md)
* [Summation Transforms](https://reference.wolfram.com/language/guide/SummationTransforms.en.md)

## History

* [Introduced in 2012 (9.0)](https://reference.wolfram.com/language/guide/SummaryOfNewFeaturesIn90.en.md) \| [Updated in 2023 (13.3)](https://reference.wolfram.com/language/guide/SummaryOfNewFeaturesIn133.en.md) ▪ [2024 (14.0)](https://reference.wolfram.com/language/guide/SummaryOfNewFeaturesIn140.en.md)