{"id":1074,"date":"2014-09-29T12:00:51","date_gmt":"2014-09-29T17:00:51","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=1074"},"modified":"2016-04-06T05:48:31","modified_gmt":"2016-04-06T10:48:31","slug":"finite-fourier-transform-matrix","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2014\/09\/29\/finite-fourier-transform-matrix\/","title":{"rendered":"Finite Fourier Transform Matrix"},"content":{"rendered":"<div class=\"content\"><!--introduction-->This is the third in a series of posts on the finite Fourier transform. The Fourier matrix produces an interesting graphic and has a surprising eigenvalue distribution.\r\n\r\n<!--\/introduction-->\r\n<h3>Contents<\/h3>\r\n<div>\r\n<ul>\r\n\t<li><a href=\"#e89a7354-5136-40c6-911a-64ab460ec1f3\">Fourier Matrix<\/a><\/li>\r\n\t<li><a href=\"#424a26d0-299f-47a0-9dcb-0e323b5ccc71\">n = 12<\/a><\/li>\r\n\t<li><a href=\"#7d7a6c84-f1ee-4b38-a551-04b25563e14b\">fftmatrix<\/a><\/li>\r\n\t<li><a href=\"#aef617ec-bdef-4858-8fe9-59e380732e17\">Eigenvalues<\/a><\/li>\r\n\t<li><a href=\"#6a78749a-d108-4c7b-97d6-daf5939e6d81\">References<\/a><\/li>\r\n<\/ul>\r\n<\/div>\r\n<h4>Fourier Matrix<a name=\"e89a7354-5136-40c6-911a-64ab460ec1f3\"><\/a><\/h4>\r\nThe Fourier matrix of order $n$ is the $n$ -by- $n$ complex Vandermonde matrix $F$ whose elements $f_{k,j}$ are powers of the $n$ th root of unity\r\n\r\n$$ \\omega = e^{-2 \\pi i\/n} $$\r\n\r\n$$ f_{k,j} = \\omega^{k j} $$\r\n\r\nThe matrix can be generated with the MATLAB statements\r\n<pre class=\"language-matlab\">k = (0:n-1)';\r\nj = (0:n-1);\r\nF = exp(-2*pi*i*k*j\/n);\r\n<\/pre>\r\nOr, by taking the FFT of the identity matrix\r\n<pre class=\"language-matlab\">F = fft(eye(n))\r\n<\/pre>\r\nThe statement\r\n<pre>plot(F)<\/pre>\r\nconnects points in the complex plane whose coordinates are the real and imaginary parts of the elements of the columns of <tt>F<\/tt>, thereby generating a subgraph of the graph on <tt>n<\/tt> points. If <tt>n<\/tt> is prime, connecting the elements of all columns generates the complete graph on <tt>n<\/tt> points. If <tt>n<\/tt> is not prime, the sparsity of the graph of all columns is related to the computational complexity, and hence the speed, of the fast FFT algorithm. The graphs for <tt>n<\/tt> = 8, 9, 10, and 11 are generating and plotted by the following code.\r\n<pre class=\"codeinput\">   <span class=\"keyword\">for<\/span> n = 8:11\r\n      subplot(2,2,n-7)\r\n      F = fft(eye(n));\r\n      plot(F)\r\n      axis <span class=\"string\">square<\/span>\r\n      axis <span class=\"string\">off<\/span>\r\n      title([<span class=\"string\">'n = '<\/span> int2str(n)])\r\n   <span class=\"keyword\">end<\/span>\r\n<\/pre>\r\n<img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/fftmatrix_blog_01.png\" alt=\"\" hspace=\"5\" vspace=\"5\" \/>\r\n\r\nBecause <tt>n = 11<\/tt> is prime, the corresponding graph shows all possible connections. But the other three values of $n$ are not prime. Some of the links in their graphs are missing, indicating that the FFT of a vector with that many points can be computed more quickly.\r\n<h4>n = 12<a name=\"424a26d0-299f-47a0-9dcb-0e323b5ccc71\"><\/a><\/h4>\r\nThe remainder of this post examines <tt>F12<\/tt> in more detail. Here is its graph.\r\n<pre class=\"codeinput\">   clf\r\n   n = 12;\r\n   F = fft(eye(n));\r\n   plot(F)\r\n   axis <span class=\"string\">square<\/span>\r\n   axis <span class=\"string\">off<\/span>\r\n   title([<span class=\"string\">'n = '<\/span> int2str(n)])\r\n<\/pre>\r\n<img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/fftmatrix_blog_02.png\" alt=\"\" hspace=\"5\" vspace=\"5\" \/>\r\n<h4>fftmatrix<a name=\"7d7a6c84-f1ee-4b38-a551-04b25563e14b\"><\/a><\/h4>\r\nThe program <tt>fftmatrix<\/tt>, <a href=\"https:\/\/www.mathworks.com\/moler\/chapters.html\">available here<\/a>, or included with the <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/37976-numerical-computing-with-matlab\">NCM App<\/a>, allows you to investigate these graphs. <tt>fftmatrix(n)<\/tt> plots all the columns of the Fourier matrix of order <tt>n<\/tt>. <tt>fftmatrix(n,j)<\/tt> plots just one column.\r\n\r\nLet's plot the individual columns of <tt>F12<\/tt>. The first column of <tt>F12<\/tt> is all ones, so its plot is just a single point.\r\n<pre class=\"codeinput\">   <span class=\"keyword\">for<\/span> j = 1:12\r\n      p = mod(j-1,4)+1;\r\n      subplot(2,2,p);\r\n      fftmatrix_mod(12,j-1)\r\n      title([<span class=\"string\">'j = '<\/span> int2str(j)])\r\n      <span class=\"keyword\">if<\/span> p == 4, snapnow, <span class=\"keyword\">end<\/span>\r\n   <span class=\"keyword\">end<\/span>\r\n<\/pre>\r\n<img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/fftmatrix_blog_03.png\" alt=\"\" hspace=\"5\" vspace=\"5\" \/> <img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/fftmatrix_blog_04.png\" alt=\"\" hspace=\"5\" vspace=\"5\" \/> <img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/fftmatrix_blog_05.png\" alt=\"\" hspace=\"5\" vspace=\"5\" \/>\r\n\r\nTo see typical behavior, look at the third subplot, the red graph labeled <tt>j = 3<\/tt>, generated by the third column\r\n<pre class=\"codeinput\">   F(:,3)\r\n<\/pre>\r\n<pre class=\"codeoutput\">ans =\r\n   1.0000 + 0.0000i\r\n   0.5000 - 0.8660i\r\n  -0.5000 - 0.8660i\r\n  -1.0000 + 0.0000i\r\n  -0.5000 + 0.8660i\r\n   0.5000 + 0.8660i\r\n   1.0000 + 0.0000i\r\n   0.5000 - 0.8660i\r\n  -0.5000 - 0.8660i\r\n  -1.0000 + 0.0000i\r\n  -0.5000 + 0.8660i\r\n   0.5000 + 0.8660i\r\n<\/pre>\r\nThese are the powers of $\\omega^2$. Because 2 divides 12 evenly these powers hit all the even-numbered points around the circle twice and miss all the odd-numbered points. Now look at the cyan graph labeled <tt>j = 11<\/tt>. These are the powers of $\\omega^{10}$, which are the complex conjugates of the powers of $\\omega^2$. So the two graphs lie on top of each other.\r\n\r\nSix of the twelve columns in the graph of <tt>F12<\/tt> connect only a subset of the nodes and ten of the columns lie on top of their complex conjugate columns. As a result, when all of the columns are combined to form the full graph, it is sparse. This sparsity, in turn, makes it possible to construct a fast finite Fourier transform algorithm for <tt>n = 12<\/tt>.\r\n<h4>Eigenvalues<a name=\"aef617ec-bdef-4858-8fe9-59e380732e17\"><\/a><\/h4>\r\nI've always been curious about the eigenvalues and vectors of the Fourier matrices. In 1979, three friends of mine at the University of New Mexico, Gus Efroymson, Art Steger, and Stan Steinberg, posed the question in the SIAM Review problem section. They didn't know that Jim McClellan and Tom Parks had actually solved their problem seven years earlier, when Jim was a grad student working under Tom at Rice. I didn't learn about the McClellan-Parks paper until fairly recently.\r\n\r\nThe Wikipedia page on the discrete Fourier transform says the facts about the eigenvalues are well known, but that the eigenvectors are the subject of ongoing research.\r\n\r\nLet's rescale $F$ so that its columns have unit length.\r\n<pre class=\"codeinput\">   F = F\/sqrt(n);\r\n<\/pre>\r\nThis makes $F' \\ F = I$\r\n<pre class=\"codeinput\">   round(F'*F)\r\n<\/pre>\r\n<pre class=\"codeoutput\">ans =\r\n     1     0     0     0     0     0     0     0     0     0     0     0\r\n     0     1     0     0     0     0     0     0     0     0     0     0\r\n     0     0     1     0     0     0     0     0     0     0     0     0\r\n     0     0     0     1     0     0     0     0     0     0     0     0\r\n     0     0     0     0     1     0     0     0     0     0     0     0\r\n     0     0     0     0     0     1     0     0     0     0     0     0\r\n     0     0     0     0     0     0     1     0     0     0     0     0\r\n     0     0     0     0     0     0     0     1     0     0     0     0\r\n     0     0     0     0     0     0     0     0     1     0     0     0\r\n     0     0     0     0     0     0     0     0     0     1     0     0\r\n     0     0     0     0     0     0     0     0     0     0     1     0\r\n     0     0     0     0     0     0     0     0     0     0     0     1\r\n<\/pre>\r\nNow $F$ is <i>unitary<\/i>, the complex generalization of <i>orthogonal<\/i>. This implies that all of its eigenvalues lie on the unit circle in the complex plane.\r\n\r\nFurthermore, it turns out that $F^4 = I$.\r\n<pre class=\"codeinput\">   round(F^4)\r\n<\/pre>\r\n<pre class=\"codeoutput\">ans =\r\n     1     0     0     0     0     0     0     0     0     0     0     0\r\n     0     1     0     0     0     0     0     0     0     0     0     0\r\n     0     0     1     0     0     0     0     0     0     0     0     0\r\n     0     0     0     1     0     0     0     0     0     0     0     0\r\n     0     0     0     0     1     0     0     0     0     0     0     0\r\n     0     0     0     0     0     1     0     0     0     0     0     0\r\n     0     0     0     0     0     0     1     0     0     0     0     0\r\n     0     0     0     0     0     0     0     1     0     0     0     0\r\n     0     0     0     0     0     0     0     0     1     0     0     0\r\n     0     0     0     0     0     0     0     0     0     1     0     0\r\n     0     0     0     0     0     0     0     0     0     0     1     0\r\n     0     0     0     0     0     0     0     0     0     0     0     1\r\n<\/pre>\r\nThis implies that any eigenvalue $\\lambda$ must satisfy $\\lambda^4$ = 1. Consequently the only possible eigenvalues are 1, -1, i, and -i. You might guess that guess that if $n$ is divisible by 4, the eigenvalues would be equally distributed among these four values. But, surprisingly, to me at least, that doesn't happen.\r\n<pre class=\"codeinput\">   lambda = eig(F)\r\n<\/pre>\r\n<pre class=\"codeoutput\">lambda =\r\n   1.0000 + 0.0000i\r\n  -1.0000 + 0.0000i\r\n  -0.0000 + 1.0000i\r\n  -1.0000 + 0.0000i\r\n  -1.0000 - 0.0000i\r\n  -0.0000 + 1.0000i\r\n   0.0000 - 1.0000i\r\n   1.0000 + 0.0000i\r\n  -0.0000 - 1.0000i\r\n   1.0000 - 0.0000i\r\n   1.0000 - 0.0000i\r\n   0.0000 - 1.0000i\r\n<\/pre>\r\nIt's hard to pick through this unsorted output, but there are four +1's, three -1's, three -i's, and only two +i's.\r\n\r\nHere is a tricky piece of code that uses <tt>angle<\/tt> and the counting feature of sparse indexing to count the number of each of the four possible eigenvalues.\r\n<pre class=\"codeinput\">   type <span class=\"string\">eigfftmat<\/span>\r\n<\/pre>\r\n<pre class=\"codeoutput\">function c = eigfftmat(n)\r\n% EIGFFTMAT Count eigenvalues of the Fourier matrix. \r\n% c = eigfftmat(n) is a 4-vector with counts for +1, -1, -i, +i.\r\n   % Compute the eigenvalues.\r\n   e = eig(fft(eye(n)));\r\n   % Sparse repeated indexing acts as a counter.\r\n   c = full(sparse(mod(round(angle(e')\/(pi\/2)),4)+1,1,1))';\r\n   c([3 2]) = c([2 3]);\r\nend\r\n   \r\n<\/pre>\r\nWhen we run this code for a sequence of values of <tt>n<\/tt>, we see the pattern predicted by the McClellan-Parks analysis. The number of each of the four possible eigenvalues depends upon <tt>floor(n\/4)<\/tt> and <tt>mod(n,4)<\/tt>.\r\n<pre class=\"codeinput\">   disp(<span class=\"string\">'     n    +1    -1    -i    +i'<\/span>)\r\n   <span class=\"keyword\">for<\/span> n = 4:20\r\n      disp([n eigfftmat(n)])\r\n   <span class=\"keyword\">end<\/span>\r\n<\/pre>\r\n<pre class=\"codeoutput\">     n    +1    -1    -i    +i\r\n     4     2     1     1\r\n     5     2     1     1     1\r\n     6     2     2     1     1\r\n     7     2     2     2     1\r\n     8     3     2     2     1\r\n     9     3     2     2     2\r\n    10     3     3     2     2\r\n    11     3     3     3     2\r\n    12     4     3     3     2\r\n    13     4     3     3     3\r\n    14     4     4     3     3\r\n    15     4     4     4     3\r\n    16     5     4     4     3\r\n    17     5     4     4     4\r\n    18     5     5     4     4\r\n    19     5     5     5     4\r\n    20     6     5     5     4\r\n<\/pre>\r\nThe proofs in the McClellan and Parks paper involve the eigenvectors and are quite complicated. It turns out that this MATLAB expression\r\n<pre class=\"language-matlab\">floor((n+[4 2 1 -1])\/4)\r\n<\/pre>\r\ngenerates a 4-vector of the multiplicities of the +1, -1, -i, and +i eigenvalues for any given value of <tt>n<\/tt>.\r\n<h4>References<a name=\"6a78749a-d108-4c7b-97d6-daf5939e6d81\"><\/a><\/h4>\r\nJ. H. McClellan and T. W. Parks, \"Eigenvalues and eigenvectors of the discrete Fourier transformation\", IEEE Trans. Audio Electroacoust 20, 66-74, <a href=\"http:\/\/dx.doi.org\/10.1109\/TAU.1972.1162342\">&lt;http:\/\/dx.doi.org\/10.1109\/TAU.1972.1162342<\/a>&gt;, 1972.\r\n\r\nG. Efroymson, A. Steger, and S.Steinberg, \"A Matrix Eigenvalue Problem\", SIAM Review, 21, 139-139, <a href=\"http:\/\/dx.doi.org\/10.1137\/1021013\">&lt;http:\/\/dx.doi.org\/10.1137\/1021013<\/a>&gt;, 1979.\r\n\r\nWikipedia, \"Discrete Fourier Transform\", <a href=\"http:\/\/en.wikipedia.org\/wiki\/Discrete_Fourier_transform\">&lt;http:\/\/en.wikipedia.org\/wiki\/Discrete_Fourier_transform<\/a>&gt;, retrieved 09\/03\/2014.\r\n\r\n<script>\/\/ <![CDATA[\r\nfunction grabCode_388d9aa73c854fff981ef56518e0562f() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='388d9aa73c854fff981ef56518e0562f ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 388d9aa73c854fff981ef56518e0562f';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2014 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('\r\n\r\n<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\r\n\r\n\r\n\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }\r\n\/\/ ]]><\/script>\r\n<p style=\"text-align: right; font-size: xx-small; font-weight: lighter; font-style: italic; color: gray;\">\r\n<a><span style=\"font-size: x-small; font-style: italic;\">Get\r\nthe MATLAB code<noscript>(requires JavaScript)<\/noscript><\/span><\/a>\r\n\r\nPublished with MATLAB\u00ae R2014a<\/p>\r\n\r\n<\/div>\r\n<!--\r\n388d9aa73c854fff981ef56518e0562f ##### SOURCE BEGIN #####\r\n%% Finite Fourier Transform Matrix\r\n% This is the third in a series of posts on the finite Fourier transform.\r\n% The Fourier matrix produces an interesting graphic and has a\r\n% surprising eigenvalue distribution.\r\n\r\n%% Fourier Matrix\r\n% The Fourier matrix of order $n$ is the $n$ -by- $n$ complex Vandermonde\r\n% matrix $F$ whose elements $f_{k,j}$ are powers of the $n$ th root of unity\r\n%\r\n% $$ \\omega = e^{-2 \\pi i\/n} $$\r\n%\r\n% $$ f_{k,j} = \\omega^{k j} $$\r\n\r\n%%\r\n% The matrix can be generated with the MATLAB statements\r\n%\r\n%   k = (0:n-1)';\r\n%   j = (0:n-1);\r\n%   F = exp(-2*pi*i*k*j\/n);\r\n%\r\n% Or, by taking the FFT of the identity matrix\r\n%\r\n%   F = fft(eye(n))\r\n%\r\n\r\n%%\r\n% The statement\r\n%\r\n%  plot(F)\r\n%\r\n% connects points in the complex plane whose coordinates are the real and\r\n% imaginary parts of the elements of the columns of |F|, thereby generating\r\n% a subgraph of the graph on |n| points.  If |n| is prime, connecting the\r\n% elements of all columns generates the complete graph on |n| points.\r\n% If |n| is not prime, the sparsity of the graph of all columns is related\r\n% to the computational complexity, and hence the speed, of the fast FFT\r\n% algorithm.  The graphs for |n| = 8, 9, 10, and 11 are generating and plotted\r\n% by the following code.\r\n\r\nfor n = 8:11\r\nsubplot(2,2,n-7)\r\nF = fft(eye(n));\r\nplot(F)\r\naxis square\r\naxis off\r\ntitle(['n = ' int2str(n)])\r\nend\r\n\r\n%%\r\n% Because |n = 11| is prime, the corresponding graph shows all possible\r\n% connections.  But the other three values of $n$ are not prime.  Some of\r\n% the links in their graphs are missing, indicating that the FFT of a\r\n% vector with that many points can be computed more quickly.\r\n\r\n%% n = 12\r\n% The remainder of this post examines |F12| in more detail.  Here is\r\n% its graph.\r\n\r\nclf\r\nn = 12;\r\nF = fft(eye(n));\r\nplot(F)\r\naxis square\r\naxis off\r\ntitle(['n = ' int2str(n)])\r\n\r\n%% fftmatrix\r\n% The program |fftmatrix|, <https:\/\/www.mathworks.com\/moler.htmlncmfilelist.html % available here>, or included with the\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/37976-numerical-computing-with-matlab % NCM App>, allows you to investigate these graphs.\r\n% |fftmatrix(n)| plots all the columns of the Fourier matrix of order |n|.\r\n% |fftmatrix(n,j)| plots just one column.\r\n\r\n%%\r\n% Let's plot the individual columns of |F12|.\r\n% The first column of |F12| is all ones, so its plot is just a single point.\r\n\r\nfor j = 1:12\r\np = mod(j-1,4)+1;\r\nsubplot(2,2,p);\r\nfftmatrix_mod(12,j-1)\r\ntitle(['j = ' int2str(j)])\r\nif p == 4, snapnow, end\r\nend\r\n\r\n%%\r\n% To see typical behavior, look at the third subplot, the red graph\r\n% labeled |j = 3|, generated by the third column\r\n\r\nF(:,3)\r\n\r\n%%\r\n% These are the powers of $\\omega^2$.  Because 2 divides 12 evenly\r\n% these powers hit all the even-numbered points around the circle twice\r\n% and miss all the odd-numbered points.  Now look at the cyan graph\r\n% labeled |j = 11|.  These are the powers of $\\omega^{10}$, which are\r\n% the complex conjugates of the powers of $\\omega^2$.  So the two\r\n% graphs lie on top of each other.\r\n\r\n%%\r\n% Six of the twelve columns in the graph of |F12| connect only a subset\r\n% of the nodes and ten of the columns lie on top of their complex conjugate\r\n% columns.  As a result, when all of the columns are combined to form the\r\n% full graph, it is sparse.  This sparsity, in turn, makes it possible to\r\n% construct a fast finite Fourier transform algorithm for |n = 12|.\r\n\r\n%% Eigenvalues\r\n% I've always been curious about the eigenvalues and vectors of the\r\n% Fourier matrices.  In 1979, three friends of mine at the University\r\n% of New Mexico, Gus Efroymson, Art Steger, and Stan Steinberg, posed\r\n% the question in the SIAM Review problem section.\r\n% They didn't know that Jim McClellan and Tom Parks had actually solved\r\n% their problem seven years earlier, when Jim was a grad student working\r\n% under Tom at Rice.  I didn't learn about the McClellan-Parks paper\r\n% until fairly recently.\r\n\r\n%%\r\n% The Wikipedia page on the discrete Fourier transform says the facts about\r\n% the eigenvalues are well known, but that the eigenvectors are the subject\r\n% of ongoing research.\r\n\r\n%%\r\n% Let's rescale $F$ so that its columns have unit length.\r\n\r\nF = F\/sqrt(n);\r\n\r\n%%\r\n% This makes $F' \\ F = I$\r\n\r\nround(F'*F)\r\n\r\n%%\r\n% Now $F$ is _unitary_, the complex generalization of _orthogonal_.\r\n% This implies that all of its eigenvalues lie on the unit circle\r\n% in the complex plane.\r\n\r\n%%\r\n% Furthermore, it turns out that $F^4 = I$.\r\n\r\nround(F^4)\r\n\r\n%%\r\n% This implies that any eigenvalue $\\lambda$ must satisfy $\\lambda^4$ = 1.\r\n% Consequently the only possible eigenvalues are 1, -1, i, and -i.\r\n% You might guess that guess that if $n$ is divisible by 4, the eigenvalues\r\n% would be equally distributed among these four values.  But, surprisingly,\r\n% to me at least, that doesn't happen.\r\n\r\nlambda = eig(F)\r\n\r\n%%\r\n% It's hard to pick through this unsorted output, but there are four +1's,\r\n% three -1's, three -i's, and only two +i's.\r\n\r\n%%\r\n% Here is a tricky piece of code that uses |angle| and the counting feature\r\n% of sparse indexing to count the number of each of the four possible\r\n% eigenvalues.\r\n\r\ntype eigfftmat\r\n\r\n%%\r\n% When we run this code for a sequence of values of |n|, we see the pattern\r\n% predicted by the McClellan-Parks analysis.  The number of each of the four\r\n% possible eigenvalues depends upon |floor(n\/4)| and |mod(n,4)|.\r\n\r\ndisp('     n    +1    -1    -i    +i')\r\nfor n = 4:20\r\ndisp([n eigfftmat(n)])\r\nend\r\n\r\n%%\r\n% The proofs in the McClellan and Parks paper involve the eigenvectors and\r\n% are quite complicated.  It turns out that this MATLAB expression\r\n%\r\n%   floor((n+[4 2 1 -1])\/4)\r\n%\r\n% generates a 4-vector of the multiplicities of the +1, -1, -i, and +i\r\n% eigenvalues for any given value of |n|.\r\n\r\n%% References\r\n% J. H. McClellan and T. W. Parks, \"Eigenvalues and eigenvectors of the\r\n% discrete Fourier transformation\", IEEE Trans. Audio Electroacoust 20, 66-74,\r\n% <http:\/\/dx.doi.org\/10.1109\/TAU.1972.1162342 % http:\/\/dx.doi.org\/10.1109\/TAU.1972.1162342>,\r\n% 1972.\r\n\r\n%%\r\n% G. Efroymson, A. Steger, and S.Steinberg, \"A Matrix Eigenvalue Problem\",\r\n% SIAM Review, 21, 139-139,\r\n% <http:\/\/dx.doi.org\/10.1137\/1021013 http:\/\/dx.doi.org\/10.1137\/1021013>,\r\n% 1979.\r\n\r\n%%\r\n% Wikipedia, \"Discrete Fourier Transform\",\r\n% <http:\/\/en.wikipedia.org\/wiki\/Discrete_Fourier_transform % http:\/\/en.wikipedia.org\/wiki\/Discrete_Fourier_transform>,\r\n% retrieved 09\/03\/2014.\r\n\r\n##### SOURCE END ##### 388d9aa73c854fff981ef56518e0562f\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img decoding=\"async\"  class=\"img-responsive\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/fftmatrix_blog_01.png\" onError=\"this.style.display ='none';\" \/><\/div><!--introduction-->This is the third in a series of posts on the finite Fourier transform. The Fourier matrix produces an interesting graphic and has a surprising eigenvalue distribution.\r\n\r\n<!--\/introduction-->... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2014\/09\/29\/finite-fourier-transform-matrix\/\">read more >><\/a><\/p>","protected":false},"author":78,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[13,4,6,16],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/1074"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/users\/78"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/comments?post=1074"}],"version-history":[{"count":5,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/1074\/revisions"}],"predecessor-version":[{"id":1391,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/1074\/revisions\/1391"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=1074"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=1074"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=1074"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}