{"id":12944,"date":"2025-06-12T16:32:59","date_gmt":"2025-06-12T20:32:59","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=12944"},"modified":"2025-12-02T15:31:01","modified_gmt":"2025-12-02T20:31:01","slug":"a-million-dollar-matrix","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2025\/06\/12\/a-million-dollar-matrix\/","title":{"rendered":"A Million Dollar Matrix"},"content":{"rendered":"<div class=\"content\"><!--introduction-->\r\n<p>The twenty-second Householder Symposium on Numerical Linear Algebra is this week, June 8 - June 13, 2025 at Cornell. My talk on Wednesday had the provocative title \"A Million-Dollar Matrix\". A PDF of the slides available at <a href=\"https:\/\/blogs.mathworks.com\/cleve\/files\/HXXII.pdf\" target=\"_blank\" rel=\"noopener\">link_1<\/a>. The talk covers posts in the Cleve's Corner blog last fall. <a href=\"https:\/\/blogs.mathworks.com\/cleve\/2024\/09\/23\/redheffer-mertens-and-one-million-dollars\/\">link_2<\/a>, <a href=\"https:\/\/blogs.mathworks.com\/cleve\/2024\/09\/27\/redheffer-and-mertens-continued\/\">link_3<\/a>, <a href=\"https:\/\/blogs.mathworks.com\/cleve\/2024\/09\/30\/redheffer-and-mertens-accelerated\/\">link_4<\/a>.<\/p>\r\n<!--\/introduction-->\r\n<h3>Contents<\/h3>\r\n<div>\r\n<ul>\r\n<li>\r\n<a href=\"#b20beddb-c979-48d3-b138-055654ab6a23\">Redheffer Matrix<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#31a779e3-af2e-4f6c-8aea-8a8cade2521f\">M&ouml;bius Function<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#f5b1cf6f-aa68-4e0f-b41e-cf1e4965f2d0\">Mertens Function<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#234e48d2-255c-42a9-b521-a14b16112aff\">Redheffer = Mertens<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#a5820505-0f5a-431b-9e47-472ebd5ac9bb\">Mertens Conjecture<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#5f9616b2-21e0-4a6f-b4e0-b2b488821f54\">Riemann Hypothesis<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#9a916f3f-a709-4abe-bb36-8b3e5633d9a7\">Riemann Computations<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#07e0dccf-c307-43f8-b34c-ecd7c8b8756c\">$1M<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#ab7c21d4-5bff-4641-b7fa-be42f5659d4b\">Spoiler<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#965e998a-f443-43c0-b630-a91fb520b436\">Redheffer Matrix<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#26a97f39-e521-4ce5-958c-33ab08907de4\">Eigenvalues<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#58ac69af-9523-48f3-9525-d76e9e21ea77\">Characteristic polynomial<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#cadabc4a-3e65-46f1-84a9-c47b74f14b13\">Jordan Canonical Form<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#00936058-7802-448f-a87b-324809a8b11d\">Code<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#d56b3299-ba0b-4be6-9eee-8e83017665c9\">Sparse Redheffer<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#0c5c10b7-3c61-4ea3-8143-6296adffcb47\">Five Ways<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#0ca7ef12-6707-47b7-b5e0-46bb24429d0e\">Complexity<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#a6ef2d9b-87aa-4b6e-85c7-08d35b9a3473\">Timing<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#5cd412ef-0cdd-40d0-addb-5f0b089fcae3\">References<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#967c8277-319f-49bc-8191-6b48a32f90da\">Thanks<\/a>\r\n<\/li>\r\n<\/ul>\r\n<\/div>\r\n<h4>Redheffer Matrix<a name=\"b20beddb-c979-48d3-b138-055654ab6a23\"><\/a>\r\n<\/h4>\r\n<p>Ray Redheffer (1921-2005) was a professor of mathematics at UCLA from 1950 until 2000. The Redheffer matrix, which he introduced in 1977, is n-by-n, with elements<\/p>\r\n<pre>   R(k,j) = 1, if j = 1 or k divides j,\r\n          = 0, otherwise<\/pre>\r\n<p>Here is a <tt>spy<\/tt> plot for n = 64. The nonzero elements lie in the first column and on diagonals with integer-valued slopes.<\/p>\r\n<p>\r\n<img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/redheffer.png\" alt=\"\"> <\/p>\r\n<h4>M&ouml;bius Function<a name=\"31a779e3-af2e-4f6c-8aea-8a8cade2521f\"><\/a>\r\n<\/h4>\r\n<p>August M&ouml;bius (1790-1868) was an eminent 19th-century German mathematician. His M&ouml;bius function is a fundamental tool in the study of prime numbers.<\/p>\r\n<pre>   mu(k) = 1 if k has an even number of distinct prime factors,\r\n         = 0 if k has a repeated prime factor,\r\n         = -1 if k has an odd number of distinct prime factors<\/pre>\r\n<p>\r\n<img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/mobius.png\" alt=\"\"> <\/p>\r\n<h4>Mertens Function<a name=\"f5b1cf6f-aa68-4e0f-b41e-cf1e4965f2d0\"><\/a>\r\n<\/h4>\r\n<p>Franz Mertens (1840-1927) was born in the Grand Duchy of Posen in the Kingdom of Prussia, which is now Poland. He lived much his life in Vienna, Austria. The Mertens function is the cumulative sum of the M&ouml;bius function.<\/p>\r\n<p>$$ M(n) = \\sum_{k = 1}^{n} \\mu(k) $$<\/p>\r\n<p>M(n) is a running count of the integers that have an even number of prime factors, minus those with an odd number of prime factors.<\/p>\r\n<p>\r\n<img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/mertens.png\" alt=\"\"> <\/p>\r\n<h4>Redheffer = Mertens<a name=\"234e48d2-255c-42a9-b521-a14b16112aff\"><\/a>\r\n<\/h4>\r\n<p>The determinant of the Redheffer matrix is equal to the Mertens function.<\/p>\r\n<p>\r\n<b>det(R(n)) = M(n)<\/b>\r\n<\/p>\r\n<p>Plots of M(n) are also plots of det(R(n)).<\/p>\r\n<h4>Mertens Conjecture<a name=\"a5820505-0f5a-431b-9e47-472ebd5ac9bb\"><\/a>\r\n<\/h4>\r\n<p>How fast does M(n) grow as n increases? Here are plots of M(n) for n in powers of 10 from n = 10 to n = 10^8, together with plots of sqrt(n) and -sqrt(n).<\/p>\r\n<p>\r\n<img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/mertens2x4.png\" alt=\"\"> <\/p>\r\n<p>We see that, at least for n &lt; 10^8,<\/p>\r\n<pre>   |M(n)| &lt; &radic;n<\/pre>\r\n<p>The Mertens conjecture is that this inequality holds for all n as n &rarr; &infin;. This conjecture is of interest because it implies the Riemann hypothesis.<\/p>\r\n<h4>Riemann Hypothesis<a name=\"5f9616b2-21e0-4a6f-b4e0-b2b488821f54\"><\/a>\r\n<\/h4>\r\n<p>The Riemann hypothesis has been called the &ldquo;Most important unsolved problem in mathematics\". Its resolution is the objective of a Clay Millenium Prize valued at one-million dollars. The hypothesis, proposed by G. F. Bernard Riemann in 1859, concerns the zeta function \u03b6(z) and the location of its zeros.<\/p>\r\n<h4>Riemann Computations<a name=\"9a916f3f-a709-4abe-bb36-8b3e5633d9a7\"><\/a>\r\n<\/h4>\r\n<p>Computation of the first N non-trivial zeros of \u03b6(s).<\/p>\r\n<pre>                authors                    year                     N\r\n   ____________________________________    ____    __________________\r\n   Riemann                                 1854                     ?\r\n   Gram                                    1903                    10\r\n   Backlund                                1914                    79\r\n   Hutchinson                              1925                   138\r\n   Titchmarsh                              1936                 1,041\r\n   Turing                                  1953                 1,104\r\n   Lehmer                                  1956                25,000\r\n   Meller                                  1958                35,337\r\n   Lehman                                  1966               250,000\r\n   Rosser, Yohe, Schoenfield               1969             3,502,500\r\n   Brent                                   1977            40,000,000\r\n   Brent                                   1979            81,000,001\r\n   Brent, Van_de_Lune, Te_Riele, Winter    1982           200,000,001\r\n   Van_de_Lune, Te_Riele, Winter           1986         1,500,000,001\r\n   Van_de_Lune                             2001       100,000,000,000\r\n   Wedeniwski                              2003       250,000,000,000\r\n   Gourdon                                 2004    10,000,000,000,000<\/pre>\r\n<h4>$1M<a name=\"07e0dccf-c307-43f8-b34c-ecd7c8b8756c\"><\/a>\r\n<\/h4>\r\n<p>The Mertens conjecture<\/p>\r\n<pre>  |M(n)| &lt; &radic;n<\/pre>\r\n<p>implies the Riemann hypothesis and is worth $1M.<\/p>\r\n<p>So, a proof that<\/p>\r\n<pre>  |det(R(n)| &lt; &radic;n<\/pre>\r\n<p>would earn R the title \"Million-Dollar Matrix\".<\/p>\r\n<h4>Spoiler<a name=\"ab7c21d4-5bff-4641-b7fa-be42f5659d4b\"><\/a>\r\n<\/h4>\r\n<p>The Mertens conjecture is false.<\/p>\r\n<p>Andrew Odlyzko and Herman te Riele (1985) prove<\/p>\r\n<pre>  limsup n&rarr;&infin; M(n)\/&radic;n &gt; 1.06<\/pre>\r\n<p>This proves the existence of infinitely many values of <tt>n<\/tt> for which<\/p>\r\n<pre>  |det(R(n))| &gt; 1.06 &radic;n<\/pre>\r\n<p>The proof is indirect. Nobody knows an actual value of <tt>n<\/tt>. Estimates are<\/p>\r\n<pre>  n &gt;&gt; 10^30<\/pre>\r\n<h4>Redheffer Matrix<a name=\"965e998a-f443-43c0-b630-a91fb520b436\"><\/a>\r\n<\/h4>\r\n<p>Even though it is not worth a million dollars, Nick Higham included the Redheffer matrix in the original MATLAB <tt>gallery<\/tt>. The command<\/p>\r\n<pre>  help private\/redheff<\/pre>\r\n<p>says<\/p>\r\n<pre>  A has N-FLOOR(LOG2(N))-1 eigenvalues equal to 1,\r\n  a real eigenvalue approximately SQRT(N),\r\n  a negative eigenvalue approximately -SQRT(N),\r\n  and the remaining eigenvalues are provably \"small\".<\/pre>\r\n<p>For n = 64, this becomes<\/p>\r\n<pre>  R(64) has 57 eigenvalues equal to 1,\r\n  a real eigenvalue approximately 8.0,\r\n  a negative eigenvalue approximately -8.0,\r\n  and the remaining eigenvalues are provably \"small\".<\/pre>\r\n<h4>Eigenvalues<a name=\"26a97f39-e521-4ce5-958c-33ab08907de4\"><\/a>\r\n<\/h4>\r\n<p>The eigenvalues of R(64) are<\/p>\r\n<pre>   eig(redheffer(64))<\/pre>\r\n<pre>   10.0445 + 0.0000i\r\n   -5.5442 + 0.0000i\r\n    0.0726 + 0.0000i\r\n    0.3213 + 0.4487i\r\n    0.3213 - 0.4487i\r\n    0.8923 + 0.1262i\r\n    0.8923 - 0.1262i<\/pre>\r\n<pre>   followed by<\/pre>\r\n<pre>    1.0000 + 0.0000i<\/pre>\r\n<pre>   repeated 57 times.<\/pre>\r\n<h4>Characteristic polynomial<a name=\"58ac69af-9523-48f3-9525-d76e9e21ea77\"><\/a>\r\n<\/h4>\r\n<p>The characteristic polynomial of R(64) is<\/p>\r\n<pre>  p(z) * (z &ndash; 1)^57<\/pre>\r\n<p>where<\/p>\r\n<pre>  p(z) = z^7 - 7^z^6 - 42*z^5 + 127*z^4 - 130*z^3 + 67*z^2 - 18*z + 1<\/pre>\r\n<h4>Jordan Canonical Form<a name=\"cadabc4a-3e65-46f1-84a9-c47b74f14b13\"><\/a>\r\n<\/h4>\r\n<p>\r\n<img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/jcf64.png\" alt=\"\"> <\/p>\r\n<h4>Code<a name=\"00936058-7802-448f-a87b-324809a8b11d\"><\/a>\r\n<\/h4>\r\n<pre class=\"codeinput\"> \r\n    type <span class=\"string\">mobius.m<\/span>\r\n<\/pre>\r\n<pre class=\"codeoutput\">\r\nfunction mu = mobius(n)\r\n    % mu = mobius(n)\r\n    mu = ones(1,n);\r\n    mu(1) = -1;\r\n    for p = primes(n)\r\n        mu(p^2:p^2:n) = 0;\r\n        mu(p:p:n) = -mu(p:p:n);\r\n    end\r\nend\r\n<\/pre>\r\n<pre class=\"codeinput\">\r\n    type <span class=\"string\">mertens.m<\/span>\r\n<\/pre>\r\n<pre class=\"codeoutput\">\r\nfunction M = mertens(n)\r\n    % M = mertens(n)\r\n    mu = mobius(n);\r\n    M = cumsum([1 mu(2:n)]);\r\nend\r\n<\/pre>\r\n<pre class=\"codeinput\">\r\n    type <span class=\"string\">redheffer.m<\/span>\r\n<\/pre>\r\n<pre class=\"codeoutput\">\r\nfunction R = redheffer(n)\r\n    % R = redheffer(n)\r\n    k = 1:n;\r\n    R = mod(k,k') == 0;\r\n    R(:,1) = 1;\r\n    R = double(R);\r\nend\r\n<\/pre>\r\n<pre class=\"codeinput\">\r\n    type <span class=\"string\">sparse_redheffer.m<\/span>\r\n<\/pre>\r\n<pre class=\"codeoutput\">\r\nfunction S = sparse_redheffer(n)\r\n    % S = sparse_redheffer(n)\r\n    j(1:n) = (1:n)';\r\n    k(1:n) = 1;\r\n    m = n;\r\n    for i = 2:n\r\n        t = [1 i:i:n]';\r\n        p = length(t);\r\n        j(m+(1:p)) = t;\r\n        k(m+(1:p)) = i;\r\n        m = m+p;\r\n    end\r\n    S = sparse(k,j,1,n,n);\r\nend\r\n<\/pre>\r\n<h4>Sparse Redheffer<a name=\"d56b3299-ba0b-4be6-9eee-8e83017665c9\"><\/a>\r\n<\/h4>\r\n<pre>     n    tictoc            bytes            nnz      sparsity      det    |det|\/&radic;n\r\n  10^1     0.000              664             36     0.3600000       -1      0.316\r\n  10^2     0.000           10,104            581     0.0581000        1      0.100\r\n  10^3     0.003          137,096          8,068     0.0080680        2      0.063\r\n  10^4     0.021        1,738,680        103,667     0.0010367      -23      0.230\r\n  10^5     0.216       21,067,992      1,266,749     0.0001267      -48      0.152\r\n  10^6     2.515      247,520,536     14,970,033     0.0000150      212      0.212\r\n  10^7    32.429    2,843,605,816    172,725,363     0.0000017     1037      0.328<\/pre>\r\n<h4>Five Ways<a name=\"0c5c10b7-3c61-4ea3-8143-6296adffcb47\"><\/a>\r\n<\/h4>\r\n<pre class=\"codeinput\">\r\n    type <span class=\"string\">fiveways<\/span>\r\n<\/pre>\r\n<pre class=\"codeoutput\">\r\nfunction M = fiveways(n)\r\n    % Five Ways to Compute the Mertens\/Redheffer Function \r\n    %1 \r\n        R = redheffer(n);\r\n        M(1) = det(R);\r\n    %2 \r\n        R =  sparse_redheffer(n);\r\n        [L,U,P,Q] = lu(R);\r\n        M(2) = det(L)*det(U)*det(P)*det(Q);\r\n    %3\r\n        R =  sparse_redheffer(n);\r\n        R(:,[1 n]) = R(:,[n 1]);\r\n        M(3) = -det(R);\r\n    %4\r\n        R =  sparse_redheffer(n);\r\n        T = R(2:n,2:n);\r\n        e = ones(1,n-1);\r\n        M(4) = 1 - e*(T\\e');\r\n    %5 \r\n        mu = mobius(n);\r\n        cmu = cumsum([1 mu(2:end)]);\r\n        M(5) = cmu(n);\r\nend   \r\n<\/pre>\r\n<h4>Complexity<a name=\"0ca7ef12-6707-47b7-b5e0-46bb24429d0e\"><\/a>\r\n<\/h4>\r\n<pre>     redheffer function  dets  complexity      M<\/pre>\r\n<pre>  #1 full      gallery     1   n^3             1\r\n  #2 sparse    lu          4   n*log(n)^2      1\r\n  #3 sparse    swap        1   n*log(n)^2      1\r\n  #4 sparse    \\           0   n*log(n)        1\r\n  #5 none      primes      0   n*log(log(n))  many<\/pre>\r\n<h4>Timing<a name=\"a6ef2d9b-87aa-4b6e-85c7-08d35b9a3473\"><\/a>\r\n<\/h4>\r\n<pre>         2e4     2e5     2e6     2e7<\/pre>\r\n<pre>   #1   26.33     -       -       -\r\n   #2    0.36   21.53     -       -\r\n   #3    0.08    1.29   16.71     -\r\n   #4    0.05    0.57    6.32   70.85\r\n   #5    0.01    0.03    0.27    3.18<\/pre>\r\n<pre>               Time (seconds)<\/pre>\r\n<h4>References<a name=\"5cd412ef-0cdd-40d0-addb-5f0b089fcae3\"><\/a>\r\n<\/h4>\r\n<div>\r\n<ul>\r\n<li>M&ouml;bius (1832), Journal f&uuml;r die reine und angewandte Mathematik.9:105&ndash;123.<\/li>\r\n<li>Riemann (1859), \"Ueber die Anzahl der Primzahlen unter einer gegebenen Gr&ouml;sse\", Monatsberichte der Berliner Akademie (1892).<\/li>\r\n<li>Mertens (1897), Akademie Wissenschaftlicher Wien Mathematik-Naturlich, IIA.106:761&ndash;830.<\/li>\r\n<li>Redheffer (1977), Numerische Methoden bei Optimierungsaufgaben, Band 3: 213&ndash;216.<\/li>\r\n<li>Odlyzko &amp; te Riele (1985), Journal f&uuml;r die reine und angewandte Mathematik 357: 138&ndash;160.<\/li>\r\n<li>Barrett &amp; Jarvis (1992), Linear Algebra and Its Applications: 162&ndash;164.<\/li>\r\n<li>Borwein (2009), <a href=\"https:\/\/blogs.mathworks.com\/cleve\/files\/Borwein.pdf\">\/\/www.cecm.sfu.ca\/~pborwein\/course\/math08\/lecture.pdf<\/a>.<\/li>\r\n<\/ul>\r\n<\/div>\r\n<h4>Thanks<a name=\"967c8277-319f-49bc-8191-6b48a32f90da\"><\/a>\r\n<\/h4>\r\n<div>\r\n<ul>\r\n<li>Tim Davis<\/li>\r\n<li>John Gilbert<\/li>\r\n<li>Pat Quillen<\/li>\r\n<li>Steve Lord<\/li>\r\n<li>Jan van Lent<\/li>\r\n<li>Frank Stenger<\/li>\r\n<li>Claude<\/li>\r\n<\/ul>\r\n<\/div>\r\n<script language=\"JavaScript\"> <!-- \r\n    function grabCode_839425f9d32346e5a88f522c7901494e() {\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='839425f9d32346e5a88f522c7901494e ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 839425f9d32346e5a88f522c7901494e';\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 2025 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>\r\n<p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\">\r\n<br>\r\n<a href=\"javascript:grabCode_839425f9d32346e5a88f522c7901494e()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript>\r\n<\/span><\/a>\r\n<br>\r\n<br>\r\n      Published with MATLAB&reg; R2024b<br>\r\n<\/p>\r\n<\/div>\r\n<!--\r\n839425f9d32346e5a88f522c7901494e ##### SOURCE BEGIN #####\r\n    %% My Talk at Householder XXII\r\n% The twenty-second Householder Symposium on \r\n% Numerical Linear Algebra is this week,\r\n% June 8 - June 13, 2025 at Cornell.\r\n% My talk on Wednesday had the provocative title\r\n% \"A Million-Dollar Matrix\".\r\n% A PDF of the slides available at\r\n% <https:\/\/blogs.mathworks.com\/cleve\/files\/HXXII.pdf\r\n% link_1>.\r\n% The talk covers posts in the Cleve's Corner blog last fall.\r\n% <https:\/\/blogs.mathworks.com\/cleve\/2024\/09\/23\/redheffer-mertens-and-one-million-dollars\/\r\n% link_2>,\r\n% <https:\/\/blogs.mathworks.com\/cleve\/2024\/09\/27\/redheffer-and-mertens-continued\/\r\n% link_3>,\r\n% <https:\/\/blogs.mathworks.com\/cleve\/2024\/09\/30\/redheffer-and-mertens-accelerated\/\r\n% link_4>.\r\n\r\n%% Redheffer Matrix\r\n% Ray Redheffer (1921-2005) was a professor of mathematics\r\n% at UCLA from 1950 until 2000.  The Redheffer matrix, which\r\n% he introduced in 1977, is n-by-n, with elements\r\n%\r\n%     R(k,j) = 1, if j = 1 or k divides j,\r\n%            = 0, otherwise\r\n%\r\n% Here is a |spy| plot for n = 64.  The nonzero elements lie\r\n% in the first column and on diagonals with integer-valued slopes.\r\n% \r\n% <<redheffer.png>>\r\n%\r\n\r\n%% M\u00f6bius Function \r\n% August M\u00f6bius (1790-1868) was an eminent 19th-century German\r\n% mathematician.  His M\u00f6bius function is a fundamental tool in\r\n% the study of prime numbers.\r\n% \r\n%     mu(k) = 1 if k has an even number of distinct prime factors,\r\n%           = 0 if k has a repeated prime factor,\r\n%           = -1 if k has an odd number of distinct prime factors\r\n%\r\n% <<mobius.png>>\r\n%\r\n\r\n%% Mertens Function\r\n% Franz Mertens (1840-1927) was born in the Grand Duchy of Posen\r\n% in the Kingdom of Prussia, which is now Poland.  He lived much\r\n% his life in Vienna, Austria.  The Mertens function is the\r\n% cumulative sum of the M\u00f6bius function.\r\n%\r\n% $$ M(n) = \\sum_{k = 1}^{n} \\mu(k) $$\r\n%\r\n% M(n) is a running count of the integers that have\r\n% an even number of prime factors, minus those with\r\n% an odd number of prime factors.\r\n%\r\n% <<mertens.png>>\r\n%\r\n\r\n%% Redheffer = Mertens\r\n% The determinant of the Redheffer matrix is equal to the Mertens\r\n% function.\r\n%\r\n% *det(R(n)) = M(n)*\r\n%\r\n% Plots of M(n) are also plots of det(R(n)).\r\n\r\n%% Mertens Conjecture\r\n% How  fast does M(n) grow as n increases?\r\n% Here are plots of M(n) for n in powers of 10 from n = 10 to n = 10^8,\r\n% together with plots of sqrt(n) and -sqrt(n). \r\n%\r\n% <<mertens2x4.png>>\r\n%\r\n\r\n%%\r\n% We see that, at least for n < 10^8,\r\n%\r\n%     |M(n)| < \u221an\r\n%\r\n% The Mertens conjecture is that this inequality holds for all n as n \u2192 \u221e.\r\n% This conjecture is of interest because it\r\n% implies the Riemann hypothesis.\r\n\r\n%% Riemann Hypothesis\r\n% The Riemann hypothesis has been called the \u201cMost important unsolved \r\n% problem in mathematics\".  Its resolution is the objective of a\r\n% Clay Millenium Prize valued at one-million dollars.\r\n% The hypothesis, proposed by G. F. Bernard Riemann in 1859,\r\n% concerns the zeta function \u03b6(z) and the location of its zeros.\r\n%\r\n\r\n%% Riemann Computations\r\n% Computation of the first N non-trivial zeros of \u03b6(s).\r\n%\r\n%                  authors                    year                     N       \r\n%     ____________________________________    ____    __________________\r\n%     Riemann                                 1854                     ?\r\n%     Gram                                    1903                    10\r\n%     Backlund                                1914                    79\r\n%     Hutchinson                              1925                   138\r\n%     Titchmarsh                              1936                 1,041\r\n%     Turing                                  1953                 1,104\r\n%     Lehmer                                  1956                25,000\r\n%     Meller                                  1958                35,337\r\n%     Lehman                                  1966               250,000\r\n%     Rosser, Yohe, Schoenfield               1969             3,502,500\r\n%     Brent                                   1977            40,000,000\r\n%     Brent                                   1979            81,000,001\r\n%     Brent, Van_de_Lune, Te_Riele, Winter    1982           200,000,001\r\n%     Van_de_Lune, Te_Riele, Winter           1986         1,500,000,001\r\n%     Van_de_Lune                             2001       100,000,000,000\r\n%     Wedeniwski                              2003       250,000,000,000\r\n%     Gourdon                                 2004    10,000,000,000,000\r\n\r\n%% $1M\r\n% The Mertens conjecture\r\n%\r\n%    |M(n)| < \u221an\r\n%\r\n% implies the Riemann hypothesis and is worth $1M. \r\n%\r\n% So, a proof that\r\n%\r\n%    |det(R(n)| < \u221an\r\n%\r\n% would earn R the title \"Million-Dollar Matrix\".\r\n\r\n%% Spoiler\r\n% The Mertens conjecture is false.\r\n%\r\n% Andrew Odlyzko and Herman te Riele (1985) prove\r\n%\r\n%    limsup n\u2192\u221e M(n)\/\u221an > 1.06\r\n%\r\n% This proves the existence of infinitely many values\r\n% of |n| for which\r\n%\r\n%    |det(R(n))| > 1.06 \u221an\r\n%\r\n% The proof is indirect.  Nobody knows an actual value of |n|.\r\n% Estimates are \r\n%\r\n%    n >> 10^30\r\n%\r\n\r\n%% Redheffer Matrix\r\n% Even though it is not worth a million dollars,\r\n% Nick Higham included the Redheffer matrix in the original\r\n% MATLAB |gallery|. The command\r\n%\r\n%    help private\/redheff\r\n% \r\n% says\r\n%\r\n%    A has N-FLOOR(LOG2(N))-1 eigenvalues equal to 1,\r\n%    a real eigenvalue approximately SQRT(N),\r\n%    a negative eigenvalue approximately -SQRT(N),\r\n%    and the remaining eigenvalues are provably \"small\".\r\n%\r\n% For n = 64, this becomes\r\n%\r\n%    R(64) has 57 eigenvalues equal to 1,\r\n%    a real eigenvalue approximately 8.0,\r\n%    a negative eigenvalue approximately -8.0,\r\n%    and the remaining eigenvalues are provably \"small\".\r\n%\r\n\r\n%% Eigenvalues\r\n% The eigenvalues of R(64) are\r\n%\r\n%     eig(redheffer(64))\r\n%   \r\n%     10.0445 + 0.0000i\r\n%     -5.5442 + 0.0000i\r\n%      0.0726 + 0.0000i\r\n%      0.3213 + 0.4487i\r\n%      0.3213 - 0.4487i\r\n%      0.8923 + 0.1262i\r\n%      0.8923 - 0.1262i  \r\n%\r\n%     followed by\r\n%\r\n%      1.0000 + 0.0000i\r\n%\r\n%     repeated 57 times.\r\n%\r\n\r\n%% Characteristic polynomial\r\n% The characteristic polynomial of R(64) is\r\n% \r\n%    p(z) * (z \u2013 1)^57\r\n%\r\n% where \r\n%\r\n%    p(z) = z^7 - 7^z^6 - 42*z^5 + 127*z^4 - 130*z^3 + 67*z^2 - 18*z + 1\r\n%\r\n\r\n%% Jordan Canonical Form\r\n%\r\n% <<jcf64.png>>\r\n\r\n\r\n%% Code\r\n%\r\n    type mobius.m\r\n\r\n%%\r\n%\r\n    type mertens.m\r\n\r\n%%\r\n%\r\n    type redheffer.m\r\n\r\n%%\r\n%\r\n    type sparse_redheffer.m\r\n\r\n%% Sparse Redheffer\r\n%  \r\n%       n    tictoc            bytes            nnz      sparsity      det    |det|\/\u221an\r\n%    10^1     0.000              664             36     0.3600000       -1      0.316\r\n%    10^2     0.000           10,104            581     0.0581000        1      0.100\r\n%    10^3     0.003          137,096          8,068     0.0080680        2      0.063\r\n%    10^4     0.021        1,738,680        103,667     0.0010367      -23      0.230\r\n%    10^5     0.216       21,067,992      1,266,749     0.0001267      -48      0.152\r\n%    10^6     2.515      247,520,536     14,970,033     0.0000150      212      0.212\r\n%    10^7    32.429    2,843,605,816    172,725,363     0.0000017     1037      0.328\r\n%        \r\n\r\n%% Five Ways\r\n%\r\n    type fiveways\r\n  \r\n%% Complexity\r\n\r\n%%\r\n%\r\n%       redheffer function  dets  complexity      M\r\n%\r\n%    #1 full      gallery     1   n^3             1\r\n%    #2 sparse    lu          4   n*log(n)^2      1\r\n%    #3 sparse    swap        1   n*log(n)^2      1\r\n%    #4 sparse    \\           0   n*log(n)        1\r\n%    #5 none      primes      0   n*log(log(n))  many\r\n\r\n%% Timing\r\n\r\n%%\r\n%           2e4     2e5     2e6     2e7\r\n%\r\n%     #1   26.33     -       -       -\r\n%     #2    0.36   21.53     -       -\r\n%     #3    0.08    1.29   16.71     -\r\n%     #4    0.05    0.57    6.32   70.85\r\n%     #5    0.01    0.03    0.27    3.18\r\n%\r\n%                 Time (seconds)\r\n\r\n%% References\r\n%\r\n% * M\u00f6bius (1832), Journal f\u00fcr die reine und angewandte Mathematik.9:105\u2013123.\r\n% * Riemann (1859), \"Ueber die Anzahl der Primzahlen unter einer gegebenen Gr\u00f6sse\",\r\n%   Monatsberichte der Berliner Akademie (1892).\r\n% * Mertens (1897), Akademie Wissenschaftlicher Wien Mathematik-Naturlich, IIA.106:761\u2013830.\r\n% * Redheffer (1977), Numerische Methoden bei Optimierungsaufgaben, Band 3: 213\u2013216.\r\n% * Odlyzko & te Riele (1985), Journal f\u00fcr die reine und angewandte Mathematik 357: 138\u2013160.\r\n% * Barrett & Jarvis (1992), Linear Algebra and Its Applications: 162\u2013164.\r\n% * Borwein (2009), <https:\/\/blogs.mathworks.com\/cleve\/files\/Borwein.pdf \r\n% \/\/www.cecm.sfu.ca\/~pborwein\/course\/math08\/lecture.pdf>.\r\n\r\n%% Thanks\r\n% * Tim Davis\r\n% * John Gilbert\r\n% * Pat Quillen\r\n% * Steve Lord\r\n% * Jan van Lent\r\n% * Frank Stenger\r\n% * Claude\r\n##### SOURCE END ##### 839425f9d32346e5a88f522c7901494e\r\n-->\r\n","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/jcf64.png\" class=\"img-responsive attachment-post-thumbnail size-post-thumbnail wp-post-image\" alt=\"\" decoding=\"async\" loading=\"lazy\" \/><\/div><!--introduction-->\r\n<p>The twenty-second Householder Symposium on Numerical Linear Algebra is this week, June 8 - June 13, 2025 at Cornell. My talk on Wednesday had the provocative title \"A Million-Dollar Matrix\". A PDF of the slides available at <a href=\"https:\/\/blogs.mathworks.com\/cleve\/files\/HXXII.pdf\" target=\"_blank\" rel=\"noopener\">link_1<\/a>. The talk covers posts in the Cleve's Corner blog last fall. <a href=\"https:\/\/blogs.mathworks.com\/cleve\/2024\/09\/23\/redheffer-mertens-and-one-million-dollars\/\">link_2<\/a>, <a href=\"https:\/\/blogs.mathworks.com\/cleve\/2024\/09\/27\/redheffer-and-mertens-continued\/\">link_3<\/a>, <a href=\"https:\/\/blogs.mathworks.com\/cleve\/2024\/09\/30\/redheffer-and-mertens-accelerated\/\">link_4<\/a>.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2025\/06\/12\/a-million-dollar-matrix\/\">read more >><\/a><\/p>","protected":false},"author":78,"featured_media":12935,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[11,13,4,6,8,36,37],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/12944"}],"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=12944"}],"version-history":[{"count":4,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/12944\/revisions"}],"predecessor-version":[{"id":13440,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/12944\/revisions\/13440"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media\/12935"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=12944"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=12944"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=12944"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}