{"id":5002,"date":"2019-07-24T14:24:12","date_gmt":"2019-07-24T19:24:12","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=5002"},"modified":"2021-01-31T14:36:47","modified_gmt":"2021-01-31T19:36:47","slug":"hadamard-matrices","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2019\/07\/24\/hadamard-matrices\/","title":{"rendered":"Hadamard Matrices"},"content":{"rendered":"<div class=\"content\"><!--introduction--><p>I have just returned from the <a title=\"Old link was https:\/\/iciam2019.org\/\">ICIAM2019 conference<\/a> in Valencia, Spain. It was a huge conference -- 4,000+ attendees, dozens of prize and invited talks, hundreds of parallel minisympsia.  I gave a talk in a two-part minisymposium organized by Nick Higham and Rob Corless. I outlined the first part of the talk in <a href=\"https:\/\/blogs.mathworks.com\/cleve\/2019\/06\/24\/bohemian-matrices-in-the-matlab-gallery\/\">this blog<\/a> a month ago.  This post outlines the second part, which was about Hadamard matrices.  Some of it is taken from a post in <a href=\"https:\/\/blogs.mathworks.com\/cleve\/2014\/08\/18\/complete-pivoting-and-hadamard-matrices\">this blog<\/a> five years ago.<\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#cb4aee7e-b963-4e7e-a9cf-fd5e6639680d\">Hadamard Matrices<\/a><\/li><li><a href=\"#19f325cd-d06d-449e-9b25-e4394ee56ac9\">Existence<\/a><\/li><li><a href=\"#d1fa7e57-8a64-4574-a61c-b03b921a772a\">Generation<\/a><\/li><li><a href=\"#15800c0d-0791-4cd3-bedb-37579d919861\">Baumert92<\/a><\/li><li><a href=\"#769bc3c9-4ffe-493b-835c-fc16ec55c140\">References<\/a><\/li><li><a href=\"#18896c73-7f3b-4487-96c4-559120e5adec\">code<\/a><\/li><\/ul><\/div><h4>Hadamard Matrices<a name=\"cb4aee7e-b963-4e7e-a9cf-fd5e6639680d\"><\/a><\/h4><p>The determinant of any matrix cannot be larger than the product of the length of its rows.  This leads to <i>Hadamard's inequality<\/i>, for any $n$ by $n$ matrix, $A$, with elements +1 or -1,<\/p><p>$|\\mbox{det}(A)| \\le n^{n\/2}$<\/p><p>A Hadamard Matrix is a square matrix $H$ with elements +1 or -1 whose rows (or columns) are mutually orthogonal, that is<\/p><p>$H^T H = nI$<\/p><p>A Hadamard matrix achieves equality in the Hadamard inequality. Conversely, any matrix achieving equality must be a Hadamard matrix.<\/p><p>A 2-by-2 Hadamard matrix is<\/p><p>$$ H = \\left( \\begin{array}{rr}\r\n   1  &amp;  1   \\\\\r\n   1  &amp;  -1  \\\\\r\n   \\end{array} \\right) $$<\/p><p>Notice that<\/p><p>$|\\mbox{det}(H)| = 2 = 2^{2\/2}$<\/p><p>A direct search of all 3-by-3 matrices shows<\/p><p>$$ A = \\left( \\begin{array}{rrr}\r\n   1  &amp;  1  &amp;  1  \\\\\r\n   1  &amp;  -1  &amp;   1 \\\\\r\n   1  &amp;  1  &amp;  -1\r\n   \\end{array} \\right) $$<\/p><p>and its permutations have the largest determinant.<\/p><p>But the rows of $A$ are not mutually orthogonal and<\/p><p>$|\\mbox{det}(A)| = 4 &lt; 3^{3\/2} = 5.196$<\/p><p>We conclude no 3-by-3 Hadamard matrices exist.<\/p><p>A 4-by-4 Hadamard is<\/p><p>$$ H = \\left( \\begin{array}{rrrr}\r\n   1  &amp;  1  &amp;  1 &amp; 1 \\\\\r\n   1  &amp;  -1  &amp;   1 &amp;   -1 \\\\\r\n   1  &amp;  1  &amp;  -1 &amp;  -1 \\\\\r\n   1  &amp;  -1  &amp;  -1  &amp;   1\r\n   \\end{array} \\right) $$<\/p><p>Notice<\/p><p>$|\\mbox{det}(H)| = 16 = 4^{4\/2}$<\/p><h4>Existence<a name=\"19f325cd-d06d-449e-9b25-e4394ee56ac9\"><\/a><\/h4><p>These three examples are special cases of this important fact: The order of a Hadamard matrix must be 1, 2, or a multiple of 4. But what about the reverse question, does a Hadamard matrix of order $n = 4k$ exist for every $k$?  Nobody knows for sure.  This is an important open mathematical problem.<\/p><h4>Generation<a name=\"d1fa7e57-8a64-4574-a61c-b03b921a772a\"><\/a><\/h4><p>It is easy to create Hadamard matrices of some sizes. If $H$ is any Hadamard matrix, then so is the block matrix<\/p><p>$$ \\left( \\begin{array}{rr}\r\n   H  &amp;  H   \\\\\r\n   H  &amp;  -H  \\\\\r\n   \\end{array} \\right) $$<\/p><p>You can start a recursion with the 1-by-1 matrix $H = 1$ and generate Hadamard matrices whose orders are powers of two.  The MATLAB function <tt>hadamard<\/tt> can also start with a 12-by-12 or a 20-by-20 $H$. Here is what you get.  Yellow is +1 and blue is -1.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/hadamard.gif\" alt=\"\"> <\/p><h4>Baumert92<a name=\"15800c0d-0791-4cd3-bedb-37579d919861\"><\/a><\/h4><p>I was present at a milestone in the history of Hadamard matrices, By 1961 it was known how to construct Hadamard matrices for all orders $n \\le 100$ that are multiples of four, except $n = 92$.  In 1961 I had a summer job at JPL, Caltech's Jet Propulsion Lab.  My office was in a temporary trailer and my trailer mate was an algebraist named Len Baumert.  Len proudly showed me a color graphic that he had just made with an hour-long computation on JPL's main-frame and that he was proposing for the cover of <i>Scientific American<\/i>.  It was a 92-by-92 matrix made up from 23-by-23 blocks of alternating light and dark cells representing +1 and -1.  The graphic didn't make the cover of <i>Scientific American<\/i>, but I kept my copy for a long time.<\/p><p>Len had filled in the last value of $n$ less than 100.  His paper with his colleagues Sol Golomb, a professor at USC, and Marshall Hall, Jr., a professor at Caltech, was published in the prestigious Bulletin of the AMS.  It turns out that I had taken a course on difference sets, the mathematics involved in generating the matrix, from Hall at Caltech.<\/p><p>Here is a MATLAB picture and code for <tt>Baumert92<\/tt>.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/Baumert92.png\" alt=\"\"> <\/p><h4>References<a name=\"769bc3c9-4ffe-493b-835c-fc16ec55c140\"><\/a><\/h4><p>Leonard Baumert, S. W. Golomb, and Marshall Hall, Jr, \"Discovery of an Hadamard Matrix of Order 92\", <a href=\"http:\/\/dx.doi.org\/10.1090%2FS0002-9904-1962-10761-7\">&lt;http:\/\/dx.doi.org\/10.1090%2FS0002-9904-1962-10761-7<\/a>&gt;, Bulletin of the American Mathematical Society 68 (1962), 237-238.<\/p><h4>code<a name=\"18896c73-7f3b-4487-96c4-559120e5adec\"><\/a><\/h4><pre class=\"codeinput\">   type <span class=\"string\">Baumert92.m<\/span>\r\n<\/pre><pre class=\"codeoutput\">\r\nfunction H = Baumert92\r\n% Baumert92  Hadamard matrix of order 92.\r\n% H = Baumert92\r\n\r\n  % Baumert, Golomb, and Hall, Bulletin AMS 68, 1962, 237-238.\r\n  % http:\/\/dx.doi.org\/10.1090%2FS0002-9904-1962-10761-7\r\n\r\n  % First row of 23-by-23 circulants.\r\n\r\n  M = [ '+ + - - - + - - - + - + + - + - - - + - - - +'\r\n        '+ - + + - + + - - + + + + + + - - + + - + + -'\r\n        '+ + + - - - + + - + - + + - + - + + - - - + +'\r\n        '+ + + - + + + - + - - - - - - + - + + + - + +' ];\r\n\r\n  M = 2*(M(:,1:2:end)=='+')-1;\r\n  \r\n  A = toeplitz([1 M(1,end:-1:2)],M(1,:));\r\n  B = toeplitz([1 M(2,end:-1:2)],M(2,:));\r\n  C = toeplitz([1 M(3,end:-1:2)],M(3,:));\r\n  D = toeplitz([1 M(4,end:-1:2)],M(4,:));\r\n\r\n  H = [A B C D; -B A -D C; -C D A -B; -D -C B A];\r\n<\/pre><script language=\"JavaScript\"> <!-- \r\n    function grabCode_0c26ca7d659141b2866d9eac37240d0b() {\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='0c26ca7d659141b2866d9eac37240d0b ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 0c26ca7d659141b2866d9eac37240d0b';\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 2019 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<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>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_0c26ca7d659141b2866d9eac37240d0b()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; R2018b<br><\/p><\/div><!--\r\n0c26ca7d659141b2866d9eac37240d0b ##### SOURCE BEGIN #####\r\n%% Hadamard Matrices\r\n% I have just returned from the\r\n% <https:\/\/iciam2019.org\/ ICIAM2019 conference> in Valencia, Spain.\r\n% It was a huge conference REPLACE_WITH_DASH_DASH 4,000+ attendees, dozens of prize and\r\n% invited talks, hundreds of parallel minisympsia.  I gave a talk in\r\n% a two-part minisymposium organized by Nick Higham and Rob Corless.\r\n% I outlined the first part of the talk in\r\n% <https:\/\/blogs.mathworks.com\/cleve\/2019\/06\/24\/bohemian-matrices-in-the-matlab-gallery\/\r\n% this blog> a month ago.  This post outlines the second part, which was \r\n% about Hadamard matrices.  Some of it is taken from a post in \r\n% <https:\/\/blogs.mathworks.com\/cleve\/2014\/08\/18\/complete-pivoting-and-hadamard-matrices\r\n% this blog> five years ago.\r\n\r\n%% Hadamard Matrices\r\n% The determinant of any matrix cannot be larger than the product of the\r\n% length of its rows.  This leads to _Hadamard's inequality_, for any\r\n% $n$ by $n$ matrix, $A$, with elements +1 or -1,\r\n%\r\n% $|\\mbox{det}(A)| \\le n^{n\/2}$\r\n\r\n%%\r\n% A Hadamard Matrix is a square matrix $H$ with elements +1 or -1 whose rows\r\n% (or columns) are mutually orthogonal, that is\r\n%\r\n% $H^T H = nI$\r\n%\r\n% A Hadamard matrix achieves equality in the Hadamard inequality.\r\n% Conversely, any matrix achieving equality must be a Hadamard matrix.\r\n\r\n%%\r\n% A 2-by-2 Hadamard matrix is\r\n%\r\n% $$ H = \\left( \\begin{array}{rr} \r\n%    1  &  1   \\\\\r\n%    1  &  -1  \\\\\r\n%    \\end{array} \\right) $$\r\n%\r\n% Notice that\r\n%\r\n% $|\\mbox{det}(H)| = 2 = 2^{2\/2}$\r\n\r\n%%\r\n% A direct search of all 3-by-3 matrices shows\r\n%\r\n% $$ A = \\left( \\begin{array}{rrr} \r\n%    1  &  1  &  1  \\\\ \r\n%    1  &  -1  &   1 \\\\\r\n%    1  &  1  &  -1  \r\n%    \\end{array} \\right) $$\r\n%\r\n% and its permutations have the largest determinant.\r\n%\r\n% But the rows of $A$ are not mutually orthogonal and\r\n%\r\n% $|\\mbox{det}(A)| = 4 < 3^{3\/2} = 5.196$\r\n%\r\n% We conclude no 3-by-3 Hadamard matrices exist.\r\n\r\n%%\r\n% A 4-by-4 Hadamard is\r\n%\r\n% $$ H = \\left( \\begin{array}{rrrr} \r\n%    1  &  1  &  1 & 1 \\\\\r\n%    1  &  -1  &   1 &   -1 \\\\\r\n%    1  &  1  &  -1 &  -1 \\\\\r\n%    1  &  -1  &  -1  &   1\r\n%    \\end{array} \\right) $$\r\n%\r\n% Notice\r\n%\r\n% $|\\mbox{det}(H)| = 16 = 4^{4\/2}$\r\n\r\n%% Existence\r\n% These three examples are special cases of this important fact:\r\n% The order of a Hadamard matrix must be 1, 2, or a multiple of 4.\r\n% But what about the reverse question, does a Hadamard matrix of order\r\n% $n = 4k$ exist for every $k$?  Nobody knows for sure.  This is an\r\n% important open mathematical problem.\r\n\r\n%% Generation\r\n% It is easy to create Hadamard matrices of some sizes.\r\n% If $H$ is any Hadamard matrix, then so is the block matrix\r\n%\r\n% $$ \\left( \\begin{array}{rr}\r\n%    H  &  H   \\\\\r\n%    H  &  -H  \\\\\r\n%    \\end{array} \\right) $$\r\n%\r\n% You can start a recursion with the 1-by-1 matrix $H = 1$ and generate\r\n% Hadamard matrices whose orders are powers of two.  The MATLAB function\r\n% |hadamard| can also start with a 12-by-12 or a 20-by-20 $H$.\r\n% Here is what you get.  Yellow is +1 and blue is -1.\r\n\r\n%%\r\n% <<hadamard.gif>>\r\n%\r\n\r\n%% Baumert92\r\n% I was present at a milestone in the history of Hadamard matrices, By 1961\r\n% it was known how to construct Hadamard matrices for all orders $n \\le 100$\r\n% that are multiples of four, except $n = 92$.  In 1961 I had a summer job\r\n% at JPL, Caltech's Jet Propulsion Lab.  My office was in a temporary trailer\r\n% and my trailer mate was an algebraist named Len Baumert.  Len proudly\r\n% showed me a color graphic that he had just made with an hour-long\r\n% computation on JPL's main-frame and that he was proposing\r\n% for the cover of _Scientific American_.  It was a 92-by-92 matrix made\r\n% up from 23-by-23 blocks of alternating light and dark cells representing\r\n% +1 and -1.  The graphic didn't make the cover of _Scientific American_,\r\n% but I kept my copy for a long time.\r\n\r\n%%\r\n% Len had filled in the last\r\n% value of $n$ less than 100.  His paper with his colleagues Sol Golomb,\r\n% a professor at USC, and Marshall Hall, Jr., a professor at Caltech,\r\n% was published in the prestigious Bulletin of the AMS.  It turns out that\r\n% I had taken a course on difference sets, the mathematics involved in \r\n% generating the matrix, from Hall at Caltech.\r\n\r\n%%\r\n% Here is a MATLAB picture and code for |Baumert92|.\r\n%\r\n% <<Baumert92.png>>\r\n%\r\n\r\n%% References\r\n% Leonard Baumert, S. W. Golomb, and Marshall Hall, Jr,\r\n% \"Discovery of an Hadamard Matrix of Order 92\",\r\n% <http:\/\/dx.doi.org\/10.1090%2FS0002-9904-1962-10761-7\r\n% http:\/\/dx.doi.org\/10.1090%2FS0002-9904-1962-10761-7>,\r\n% Bulletin of the American Mathematical Society 68 (1962), 237-238.\r\n\r\n%% code\r\n\r\n   type Baumert92.m\r\n\r\n##### SOURCE END ##### 0c26ca7d659141b2866d9eac37240d0b\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img decoding=\"async\"  class=\"img-responsive\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/hadamard.gif\" onError=\"this.style.display ='none';\" \/><\/div><!--introduction--><p>I have just returned from the <a title=\"Old link was https:\/\/iciam2019.org\/\">ICIAM2019 conference<\/a> in Valencia, Spain. It was a huge conference -- 4,000+ attendees, dozens of prize and invited talks, hundreds of parallel minisympsia.  I gave a talk in a two-part minisymposium organized by Nick Higham and Rob Corless. I outlined the first part of the talk in <a href=\"https:\/\/blogs.mathworks.com\/cleve\/2019\/06\/24\/bohemian-matrices-in-the-matlab-gallery\/\">this blog<\/a> a month ago.  This post outlines the second part, which was about Hadamard matrices.  Some of it is taken from a post in <a href=\"https:\/\/blogs.mathworks.com\/cleve\/2014\/08\/18\/complete-pivoting-and-hadamard-matrices\">this blog<\/a> five years ago.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2019\/07\/24\/hadamard-matrices\/\">read more >><\/a><\/p>","protected":false},"author":78,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[4,6],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/5002"}],"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=5002"}],"version-history":[{"count":4,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/5002\/revisions"}],"predecessor-version":[{"id":6599,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/5002\/revisions\/6599"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=5002"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=5002"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=5002"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}