I really like the Householder matrix. I’ve blogged about its ability to generate an orthonormal basis containing a particular vector in a previous blog post. This blog post is a bit of a tutorial which will use the Householder matrix to perform a QR decomposition. Applying Householder reflectors to compute a QR decomposition is nothing new, but I want this blog post to attempt to provide some intuition into how the algorithm works starting from almost nothing. We’ll briefly visit inner products, matrix multiplication, the Householder matrix and then build a QR decomposition in C. I’m not going to use formal language to define these operations unless it’s necessary. I’m going to assume that you understand things like matrix multiplication and what a matrix inverse is, but not much more than that. The post will be written assuming complex numbers are being used (the C implementation will not… maybe I will add one later).
The inner product
The inner product takes two vectors and produces a scalar. You can think of a vector as being an array of length 
values representing coordinates in some N-dimensional space.
![\[ \langle \mathbf{a}, \mathbf{b} \rangle = \sum^{N}_{k=1} a_k \overline{b_k} \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-1ae9b8fbc8f1d2ee4e88416abc7a77e9_l3.png "Rendered by QuickLaTeX.com")
Note the bar in the above indicates conjugation. If 
and 
are row vectors, we could write the above as:
![\[ \langle \mathbf{a}, \mathbf{b} \rangle = \mathbf{a} \mathbf{b}^H \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-a0c1fed43cca097a24c9d8f9140090c4_l3.png "Rendered by QuickLaTeX.com")
Where 
is the transposed conjugate of . Two vectors are said to be orthogonal if they have an inner product of zero. If the inner product of a vector with itself is equal to one, the vector is said to be a unit-vector. The inner product of a vector with a unit-vector is the proportion of that vector that is pointing in the same direction as the unit-vector i.e. if 
is some unit vector and I define a new vector as:
![\[ \mathbf{b} = \mathbf{a} - \langle \mathbf{a}, \mathbf{u} \rangle \mathbf{u} \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-55fdeac64929df5ec9fe6d9a76c516cd_l3.png "Rendered by QuickLaTeX.com")
The vector is now orthogonal to i.e. 
.
There are some good geometric visualisations of these for two and three dimensional vectors… but everything continues to work in arbitrary dimensions. The above image contains two plots which both contain two perpendicular unit vectors (red and green) and an arbitrary vector (black). In both plots we can verify the red and green vectors are unit vectors by applying the inner product. We can also verify they are orthogonal by applying the inner product. If we compute the inner product of the black vector on the two unit vectors, then multiply each of the scalar results by the corresponding unit vectors used to compute them and sum the results, we should get back the black vector.
Matrix multiplications
We can define matrix multiplication using inner products of the vectors which make up the rows of the left-hand side matrix with the vectors which make up the columns of the right-hand side matrix.
![\[ \begin{tiny} \begin{pmatrix} \langle r_0, \overline{c_0} \rangle & \langle r_0, \overline{c_1} \rangle & \dots & \langle r_0, \overline{c_{N-1}} \rangle \\ \langle r_1, \overline{c_0} \rangle & \langle r_1, \overline{c_1} \rangle & \dots & \langle r_1, \overline{c_{N-1}} \rangle \\ \vdots & \vdots & & \vdots \\ \langle r_{M-1}, \overline{c_0} \rangle & \langle r_{M-1}, \overline{c_1} \rangle & \dots & \langle r_{M-1}, \overline{c_{N-1}} \rangle \end{pmatrix} = \begin{pmatrix} \dots & r_0 & \dots \\ \dots & r_1 & \dots \\ & \vdots & \\ \dots & r_{M-1} & \dots \end{pmatrix} \begin{pmatrix} \vdots & \vdots & & \vdots \\ c_0 & c_1 & \dots & c_{N-1} \\ \vdots & \vdots & & \vdots \end{pmatrix} \end{tiny} \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-c7ddaa91d6317da79c975c941762bfdc_l3.png "Rendered by QuickLaTeX.com")
We can use this to demonstrate that a matrix that is made up of rows (or columns) that are all orthogonal to each other is trivially invertible – particularly if the vectors are unit vectors, in which case the inverse of matrix 
is 
. To make this particularly clear:
![\[ \begin{tiny} \begin{pmatrix} \langle r_0, r_0 \rangle & \langle r_0, r_1 \rangle & \dots & \langle r_0, r_{N-1} \rangle \\ \langle r_1, r_0 \rangle & \langle r_1, r_1 \rangle & \dots & \langle r_1, r_{N-1} \rangle \\ \vdots & \vdots & & \vdots \\ \langle r_{N-1}, r_0 \rangle & \langle r_{N-1}, r_1 \rangle & \dots & \langle r_{N-1}, r_{N-1} \rangle \end{pmatrix} = \begin{pmatrix} \dots & r_0 & \dots \\ \dots & r_1 & \dots \\ & \vdots & \\ \dots & r_{N-1} & \dots \end{pmatrix} \begin{pmatrix} \vdots & \vdots & & \vdots \\ \overline{r_0} & \overline{r_1} & \dots & \overline{r_{N-1}} \\ \vdots & \vdots & & \vdots \end{pmatrix} \end{tiny} \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-8887a7632397e34bcd9a5ea13da027c1_l3.png "Rendered by QuickLaTeX.com")
If the rows are orthogonal to each other, the inner products off the main diagonal will all be zero. If the rows are unit vectors, the diagonal entries are by definition 1 and 
.
The Householder matrix
Define a matrix 
as:
![\[\mathbf{P}=\mathbf{I} - 2\mathbf{v}\mathbf{v}^H\]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-233f58c7b1ba1b8a5b50df325f9a8281_l3.png "Rendered by QuickLaTeX.com")
Where 
is a unit vector. Then:
![\[\begin{array}{@{}ll@{}} \mathbf{P}\mathbf{P} &= \mathbf{I}-2\left(\mathbf{v}\mathbf{v}^H+\mathbf{v}\mathbf{v}^H\right)+4\mathbf{v}\mathbf{v}^H\mathbf{v}\mathbf{v}^H \\ &= \mathbf{I}-4\mathbf{v}\mathbf{v}^H+4\mathbf{v}\left(\mathbf{v}^H\mathbf{v}\right)\mathbf{v}^H \\ & = \mathbf{I} \end{array}\]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-8acb0f1ebfdbff896bb8a873981294c0_l3.png "Rendered by QuickLaTeX.com")
Thereore is its own inverse (
) and must also be unitary (
).
If we can work out a method to choose such that will contain a particular unit vector and we multiply by any scaled version of vector , we will get a vector which has only one non-zero entry (because all other rows of the matrix will be orthogonal to ). I have described this process before in a previous blog post but will repeat it here with some more detail. Define a vector that we want the first column of to equal:
![\[ \begin{array}{@{}ll@{}} \mathbf{u} &= \left( \mathbf{I} - 2 \mathbf{v} \mathbf{v}^H \right) \mathbf{e}_1 \\ \frac{\mathbf{e}_1-\mathbf{u}}{2} &= \mathbf{v} \overline{v_1} \end{array} \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-d8c995be3d28f6fb8e0373d8ce3e9c49_l3.png "Rendered by QuickLaTeX.com")
If 
is real, we can break into its individual coordinates to solve for their values:
![\[ \begin{array}{@{}ll@{}} v_1 &= \sqrt{\frac{1-u_1}{2}} \\ v_2 &= \frac{-u_2}{2\sqrt{\frac{1-u_1}{2}}} \\ &\vdots \\ v_n &= \frac{-u_n}{2\sqrt{\frac{1-u_1}{2}}} \end{array} \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-e8f67be1993b04ef84fcd1029bf36a35_l3.png "Rendered by QuickLaTeX.com")
Given the way the matrix is defined, the computation of the square root is unnecessary in an implementation. This is best seen if we expand out the 
matrix:
![\[ \begin{array}{@{}ll@{}} 2 \mathbf{v} \mathbf{v}^H &= \begin{pmatrix} 2 v_1 \overline{v_1} & 2 v_1 \overline{v_2} & \dots & 2 v_1 \overline{v_n} \\ 2 v_2 \overline{v_1} & 2 v_2 \overline{v_2} & \dots & 2 v_2 \overline{v_n} \\ \vdots & \vdots & \ddots & \vdots \\ 2 v_n \overline{v_1} & 2 v_n \overline{v_2} & \dots & 2 v_n \overline{v_n} \end{pmatrix} \\ &= \begin{pmatrix} 1 - u_1 & -\overline{u_2} & \dots & -\overline{u_n} \\ -u_2 & \frac{u_2 \overline{u_2}}{1-u_1} & \dots & \frac{u_2 \overline{u_n}}{1-u_1} \\ \vdots & \vdots & \ddots & \vdots \\ -u_n & \frac{u_n \overline{u_2}}{1-u_1} & \dots & \frac{u_n \overline{u_n}}{1-u_1} \end{pmatrix} \end{array} \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-97a3d1a59705e62fd3fde662e1a02368_l3.png "Rendered by QuickLaTeX.com")
Define a scalar 
and a vector 
:
![\[\mathbf{w} = \begin{pmatrix}1 - u_1 \\ -u_2 \\ \vdots \\ -u_n \end{pmatrix} \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-eccab58f13e264d6907a94bece40cc63_l3.png "Rendered by QuickLaTeX.com")
Then 
. This is a particularly useful formulation because we rarely want to compute in its entirity and perform a matrix mutliplication. Rather, we compute:
![\[ \mathbf{P}\mathbf{A} = \left(\mathbf{I}-\alpha\mathbf{w}\mathbf{w}^H\right)\mathbf{A}=\mathbf{A}-\alpha\mathbf{w}\mathbf{w}^H\mathbf{A} \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-99503d0e9d9b736425eab890dac578a9_l3.png "Rendered by QuickLaTeX.com")
Which is substantially more efficient. A final necessary change is necessary: if is close to one (which implies all other coefficients of are approaching zero), 
will begin to approach infinity. There is a relatively simple change here which is to recognise that and 
are parallel but pointing in different directions (their inner-product is -1). If we don’t care about the direction of the vector, we can change its sign to be the most numerically suitiable for the selection of i.e. if 
use otherwise use .
This is actually very useful in many applications, one of which is the QR decomposition.
The QR decomposition
The QR decomposition breaks down a matrix into a unitary matrix 
and an upper-triangular matrix 
. There are a number of ways to do this, but we are going use the Householder matrix.
![\[\mathbf{A} = \mathbf{Q}\mathbf{R}\]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-3c72f1fe6262984bf4cc133a276c46af_l3.png "Rendered by QuickLaTeX.com")
Let’s start by defining a series of unitary transformations applied to as:
![\[\begin{array}{@{}ll@{}} \mathbf{X}_1&=\mathbf{P}_N \mathbf{A} \\ \mathbf{X}_{2} &= \begin{pmatrix} \mathbf{I}_{1} & \mathbf{0} \\ \mathbf{0} & \mathbf{P}_{N-1} \end{pmatrix} \mathbf{X}_{1} \\ \mathbf{X}_{3} &= \begin{pmatrix} \mathbf{I}_{2} & \mathbf{0} \\ \mathbf{0} & \mathbf{P}_{N-2} \end{pmatrix} \mathbf{X}_{2} \\ & \vdots \\ \mathbf{X}_{N-1} &= \begin{pmatrix} \mathbf{I}_{N-2} & \mathbf{0} \\ \mathbf{0} & \mathbf{P}_{2} \end{pmatrix} \mathbf{X}_{N-2} \end{array} \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-769b140ee4ea59eca2c00fe6ff3fd949_l3.png "Rendered by QuickLaTeX.com")
Where 
are all n-by-n unitary matrices. Notice that the first row of 
will be unmodified by all the transforms that follow. The first two rows of 
will be unmodified by all the transforms that follow – and so-on.
If we can somehow force the first row of 
to be the first column of scaled to be a unit vector (while keeping unitary), the first column of will contain only one non-zero entry. We then set about finding a way to select 
such that the second column contains only two non-zero entries… and so on. Once the process is finished, 
is upper triangular and the unitary matrix which converts into this form can be written as:
![\[ \mathbf{Q}^H = \begin{pmatrix} \mathbf{I}_{N-2} & \mathbf{0} \\ \mathbf{0} & \mathbf{P}_{2} \end{pmatrix} \dots \begin{pmatrix} \mathbf{I}_{2} & \mathbf{0} \\ \mathbf{0} & \mathbf{P}_{N-2} \end{pmatrix} \begin{pmatrix} \mathbf{I}_{1} & \mathbf{0} \\ \mathbf{0} & \mathbf{P}_{N-1} \end{pmatrix} \mathbf{P}_N \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-9eef7c46587efa085cb4e4fec7c83067_l3.png "Rendered by QuickLaTeX.com")
And:
![\[ \begin{array}{@{}ll@{}} \mathbf{X}_{N-1} &= \mathbf{Q}^H\mathbf{A} \\ \mathbf{Q}\mathbf{X}_{N-1}&=\mathbf{A} \end{array} \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-27725630489b45946e6fbe64c725f6fb_l3.png "Rendered by QuickLaTeX.com")
When we follow the above process and the matricies are chosen to be Householder matrices, we have performed the QR decomposition using Householder matrices.
Follows is the C code that implements the decomposition. Because the algorithm repeatedly applies transformations to to eventually arrive at , we will design an API that operates in-place on the supplied matrix. The orthogonal matrix will be built in parallel. The N-1 iterations over the i variable, correspond to the N-1 transformation steps presented earlier. I make no claims about the computational performance of this code. The numerical performance could be improved by using a different method to compute the length of the vector (first thing that happens in the column loop).
/* Perform the QR decomposition of the given square A matrix. * A/R is stored and written in columns i.e. * a[0] a[3] a[6] * a[1] a[4] a[7] * a[2] a[5] a[8] * * q is stored in rows i.e. * q[0] q[1] q[2] * q[3] q[4] q[5] * q[6] q[7] q[8] */ void qr(double *a_r, double *q, int N) { int i, j, k; /* Initialise qt to be the identity matrix. */ for (i = 0; i < N; i++) { for (j = 0; j < N; j++) { q[i*N+j] = (i == j) ? 1.0 : 0.0; } } for (i = 0; i < N-1; i++) { double norm, invnorm, alpha; double *ccol = a_r + i*N; /* Compute length of vector (needed to perform normalisation). */ for (norm = 0.0, j = i; j < N; j++) { norm += ccol[j] * ccol[j]; } norm = sqrt(norm); /* Flip the sign of the normalisation coefficient to have the * effect of negating the u vector. */ if (ccol[0] > 0.0) norm = -norm; invnorm = 1.0 / norm; /* Normalise the column * Convert the column in-place into the w vector * Compute alpha */ ccol[i] = (1.0 - ccol[i] * invnorm); for (j = i+1; j < N; j++) { ccol[j] = -ccol[j] * invnorm; } alpha = 1.0 / ccol[i]; /* Update the orthogonal matrix */ for (j = 0; j < N; j++) { double acc = 0.0; for (k = i; k < N; k++) { acc += ccol[k] * q[k+j*N]; } acc *= alpha; for (k = i; k < N; k++) { q[k+j*N] -= ccol[k] * acc; } } /* Update the upper triangular matrix */ for (j = i+1; j < N; j++) { double acc = 0.0; for (k = i; k < N; k++) { acc += ccol[k] * a_r[k+j*N]; } acc *= alpha; for (k = i; k < N; k++) { a_r[k+j*N] -= ccol[k] * acc; } } /* Overwrite the w vector with the column data. */ ccol[i] = norm; for (j = i+1; j < N; j++) { ccol[j] = 0.0; } } } |
The algorithm follows almost everthing described on this page – albiet with some minor obfuscations (the vector is stored temporarily in the output matrix to avoid needing any extra storage). It’s worth mentioning that the first step of initialising the matrix to 
isn’t necessary. The initialisation could be performed explicitly in the first iteration of the loop over i – but that introduces more conditional code.
) and we knew one point where the release was perfectly aligned (
), we know that we could cross-fade into the start of the release at:![\[ \forall n \in \mathbb Z, t = t_r + T n \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-5e556700352b609fa1ca94b364e36682_l3.png "Rendered by QuickLaTeX.com")
) for an 
. The symmetry is even around 
and odd around 
and holds for every basis function of the DCT-4. i.e. The DCT-4 assumes that the input data continues on forever, repeating itself in the following manner: 
, 
, 
, 
.
real data points and produces ![\[ X_k = \displaystyle\sum\limits_{n=0}^{2N-1} x_n \cos \frac{ \pi \left( n + 0.5 + N/2 \right) \left( k + 0.5 \right) }{N} \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-b5f06b73187053de041101098dac85b1_l3.png "Rendered by QuickLaTeX.com")
length sequences 
, 
, 
and 
. The total length of this sequence is 
to denote a reversal of the sequence):![\[ - c_r - d , a - b_r \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-d6e3819126ececb9dcc5056ba24c418f_l3.png "Rendered by QuickLaTeX.com")
![\[ x_n = \frac{1}{N} \displaystyle\sum\limits_{n=0}^{N-1} X_k \cos \frac{ \pi \left( n + 0.5 + N/2 \right) \left( k + 0.5 \right) }{N} \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-0e5ac53bdbfa2e5a94a9c3ef1ac4955b_l3.png "Rendered by QuickLaTeX.com")
![\[ u, v, v_r, u_r \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-1d66ef24f43017c720511a1b180f1f32_l3.png "Rendered by QuickLaTeX.com")
![\[ c = v_r \left( d_r u + c v_r \right) + u \left( c u - d_r v_r \right) \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-4e809d7db0cbbd58a1b649f19ea004c5_l3.png "Rendered by QuickLaTeX.com")
![\[ d = u_r \left( d u_r + c_r v \right) + v \left( d v - c_r u_r \right) \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-f5d9beeb5eafcfb7743c1d95c939f9b9_l3.png "Rendered by QuickLaTeX.com")
(which implies in this case that 
must also be true).![\[ w_n = \sin \frac{ \pi \left( n + 0.5 \right) }{2N} \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-494eb5ec723a8fe31cc77398fdc847a1_l3.png "Rendered by QuickLaTeX.com")
![\[ X_k = \displaystyle\sum\limits_{n=0}^{N-1} x_n \cos \frac{ \pi \left( n + \frac{1}{2} \right) \left( k + \frac{1}{2} \right) }{N} \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-2f8633ed18a9c1fb33b866414d9c9fe1_l3.png "Rendered by QuickLaTeX.com")
into a complex exponential and obtain the following:![\[ X_k = \Re \left\{ \displaystyle\sum\limits_{n=0}^{N-1} x_n \mathrm{e}^{\frac{\mathrm{j} \pi \left( n + \frac{1}{2} \right) \left( k + \frac{1}{2} \right) }{N}} \right\} \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-7da9eda74ef007fa48e3429708ce6660_l3.png "Rendered by QuickLaTeX.com")
and 
. The second sequence is reversed and decimated because when the 
is replaced by 
in the 
term of the exponential, the expression is negated rather than the offset being modified. We move the ![\[ X_k = \Re \left\{ \displaystyle\sum\limits_{n=0}^{N/2-1} x_{2n} \mathrm{e}^{\frac{\mathrm{j} \pi \left( 2n + \frac{1}{2} \right) \left( k + \frac{1}{2} \right) }{N}} + x_{N-1-2n} \mathrm{e}^{- \frac{\mathrm{j} \pi \left( 2n + \frac{1}{2} \right) \left( k + \frac{1}{2} \right) }{N}} \mathrm{e}^{\mathrm{j} \pi \left( k + \frac{1}{2} \right)} \right\} \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-73cb66363e494f30b9c795f5aed013c2_l3.png "Rendered by QuickLaTeX.com")
![\[ X_k = \Re \left\{ \displaystyle\sum\limits_{n=0}^{N/2-1} x_{2n} \mathrm{e}^{\frac{\mathrm{j} \pi \left( 2n + \frac{1}{2} \right) \left( k + \frac{1}{2} \right) }{N}} + \mathrm{j} {\left( -1 \right)}^{k} x_{N-1-2n} \mathrm{e}^{- \frac{\mathrm{j} \pi \left( 2n + \frac{1}{2} \right) \left( k + \frac{1}{2} \right) }{N}} \right\} \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-7f6e9fdd8083f6329181cf61eb107def_l3.png "Rendered by QuickLaTeX.com")
into the terms 
and 
. Again we choose to reverse the second sequence because it will keep the exponential terms in a similar but negated form.![\[ X_{2k} = \Re \left\{ \displaystyle\sum\limits_{n=0}^{N/2-1} x_{2n} \mathrm{e}^{\frac{\mathrm{j} \pi \left( 2n + \frac{1}{2} \right) \left( 2k + \frac{1}{2} \right) }{N}} + \mathrm{j} x_{N-1-2n} \mathrm{e}^{- \frac{\mathrm{j} \pi \left( 2n + \frac{1}{2} \right) \left( 2k + \frac{1}{2} \right) }{N}} \right\} \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-dc4b7b88615a6a9109c479822fc5d184_l3.png "Rendered by QuickLaTeX.com")
![\[ X_{N-1-2k} = \Re \left\{ \displaystyle\sum\limits_{n=0}^{N/2-1} \mathrm{j} x_{2n} \mathrm{e}^{- \frac{\mathrm{j} \pi \left( 2n + \frac{1}{2} \right) \left( 2k + \frac{1}{2} \right) }{N}} - x_{N-1-2n} \mathrm{e}^{\frac{\mathrm{j} \pi \left( 2n + \frac{1}{2} \right) \left( 2k + \frac{1}{2} \right) }{N}} \right\} \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-854116fb7812a75cea69c48ddba12720_l3.png "Rendered by QuickLaTeX.com")
![\[ X_{2k} = \Re \left\{ \displaystyle\sum\limits_{n=0}^{N/2-1} \left( x_{2n} + \mathrm{j} x_{N-1-2n} \right) \mathrm{e}^{- \frac{\mathrm{j} \pi \left( 2n + \frac{1}{2} \right) \left( 2k + \frac{1}{2} \right) }{N}} \right\} \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-fb1748ab99f079ff90cb8a97803061ab_l3.png "Rendered by QuickLaTeX.com")
![\[ X_{N-1-2k} = \Re \left\{ \displaystyle\sum\limits_{n=0}^{N/2-1} \left( \mathrm{j} x_{2n} - x_{N-1-2n} \right) \mathrm{e}^{- \frac{\mathrm{j} \pi \left( 2n + \frac{1}{2} \right) \left( 2k + \frac{1}{2} \right) }{N}} \right\} \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-0bcb8fa72fa08b3a576d49cd305cc839_l3.png "Rendered by QuickLaTeX.com")
, we get:![\[ X_{N-1-2k} = - \Im \left\{ \displaystyle\sum\limits_{n=0}^{N/2-1} \left( x_{2n} + \mathrm{j} x_{N-1-2n} \right) \mathrm{e}^{- \frac{\mathrm{j} \pi \left( 2n + \frac{1}{2} \right) \left( 2k + \frac{1}{2} \right) }{N}} \right\} \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-a44782d406939012a5c9049ec8a6e022_l3.png "Rendered by QuickLaTeX.com")
![\[ X_{2k} = \Re \left\{ \mathrm{e}^{- \frac{\mathrm{j} \pi \left( 2k + \frac{1}{2} \right) }{2N}} \displaystyle\sum\limits_{n=0}^{N/2-1} \left( x_{2n} + \mathrm{j} x_{N-1-2n} \right) \mathrm{e}^{- \frac{\mathrm{j} \pi n}{N}} \mathrm{e}^{- \frac{\mathrm{j} 2 \pi n k }{N/2}} \right\} \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-ef33a88c8ce844b7c2839bcb186ed618_l3.png "Rendered by QuickLaTeX.com")
![\[ X_{N-1-2k} = - \Im \left\{ \mathrm{e}^{- \frac{\mathrm{j} \pi \left( 2k + \frac{1}{2} \right) }{2N}} \displaystyle\sum\limits_{n=0}^{N/2-1} \left( x_{2n} + \mathrm{j} x_{N-1-2n} \right) \mathrm{e}^{- \frac{\mathrm{j} \pi n}{N}} \mathrm{e}^{- \frac{\mathrm{j} 2 \pi n k }{N/2}} \right\} \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-f90d954f6d12e6f46cd89e972da96c22_l3.png "Rendered by QuickLaTeX.com")
.
by 
.
, the DFT of the sequence 
.
by 
.![\[ X_k = \left\{ \begin{array}{l l} \Re \left\{ Y_{k/2} \right\} & \quad \text{for even $k$} \\ - \Im \left\{ Y_{(N-1-k)/2} \right\} & \quad \text{for odd $k$} \end{array} \right. \]](https://www.appletonaudio.com/wp-content/ql-cache/quicklatex.com-4c2081cb6496efa71aee52e805c2c9bd_l3.png "Rendered by QuickLaTeX.com")