[{"id":247851,"date":"2026-09-04T09:16:16","date_gmt":"2026-09-04T14:16:16","guid":{"rendered":"https:\/\/www.johndcook.com\/blog\/?p=247851"},"modified":"2026-09-04T09:20:10","modified_gmt":"2026-09-04T14:20:10","slug":"stable-rank","status":"publish","type":"post","link":"https:\/\/www.johndcook.com\/blog\/2026\/09\/04\/stable-rank\/","title":{"rendered":"Computing a lower bound on matrix rank"},"content":{"rendered":"

Suppose you want to know the rank of an n<\/em> \u00d7 n<\/em> matrix A<\/em>, the number of linearly independent rows of\u00a0A<\/em>, or equivalently the number of linearly independent columns. There are at least three difficulties.<\/p>\n

Difficulties in computing rank<\/h2>\n

First of all, rank is not a continuous function of a matrix. Since rank is an integer, an arbitrarily small change in the matrix could cause a discrete change in the rank [1]. A small error in computing\u00a0A<\/em> could produce a matrix with a different rank.<\/p>\n

Second, finding the rank takes O<\/em>(n<\/em>\u00b3) operations, which may or may not be an issue depending on context.<\/p>\n

Third, you may not have the matrix\u00a0A<\/em> in an explicit form. Maybe you’re able to compute products\u00a0Av<\/em> for vectors\u00a0v<\/em> but it’s not practical to form the entire matrix\u00a0A<\/em>.<\/p>\n

Rank-trace inequality<\/h2>\n

If you don’t need to know the rank of\u00a0A<\/em> per se, but only need to know whether it is above a certain size, a lower bound on the rank may enough.<\/p>\n

Suppose\u00a0A<\/em> is a Hermitian matrix. If\u00a0A<\/em> is real, this means\u00a0A<\/em> is symmetric. If\u00a0A<\/em> is complex, this means\u00a0A<\/em> equals its conjugate transpose. Then the rank-trace inequality says<\/p>\n

\"\\operatorname{rank}(A)\\ge\\frac{(\\operatorname{tr}
\nThe quantity on the right hand side is known as the stable rank<\/strong> of\u00a0A<\/em>. It’s not a rank in any algebraic sense, but it gives a lower bound on rank. And it solves the three problems listed above.<\/p>\n

Stability<\/h3>\n

First of all, trace\u00a0is<\/em> a continuous function of a matrix, and so stable rank is also a continuous function of a matrix, provided the denominator isn’t zero. A small change to a matrix only makes a small change to its stable rank. That’s why stable rank is called stable.<\/p>\n

Efficiency<\/h3>\n

Second, although computing rank takes O<\/em>(n<\/em>\u00b3) operations, computing stable rank\u00a0takes only O<\/em>(n<\/em>\u00b2) operations, though this isn’t immediately obvious.<\/p>\n

The trace of A<\/em> takes n<\/em> operations: simply sum the elements on the diagonal of A<\/em>. But how do you take the trace of A<\/em>\u00b2? Squaring A<\/em> takes n<\/em>\u00b3 operations, and so if you had to square A<\/em> to find the trace of A<\/em>\u00b2 the rank-trace inequality would have no efficiency advantage over finding the rank of A<\/em>. But you can compute the trace of A<\/em>\u00b2 via<\/p>\n

\"\\operatorname{tr}(A^2)<\/p>\n

Formation<\/h3>\n

Now suppose you don’t have the matrix A<\/em> per se but you do have a way of probing A<\/em>, computing the product of vectors with A<\/em>. Maybe A<\/em> is too large to fit into memory, or explicitly computing the elements of A<\/em> would take too long.<\/p>\n

There are Monte Carlo algorithms for estimating the traces of A<\/em> and A<\/em>\u00b2 that could be used together to estimate the stable rank of A<\/em>.<\/p>\n

Demonstration<\/h2>\n

The following Python code illustrates the discussion above.<\/p>\n

import numpy as np\r\n\r\nnp.random.seed(20260904)\r\nn = 5\r\nB = np.random.randn(n, n)\r\nA = B.T @ B + 1e-8 * np.eye(n)  # Gram matrix plus a tiny shift => SPD\r\n\r\nrank_A = np.linalg.matrix_rank(A)\r\ntr_A = np.trace(A)\r\ntr_A2 = np.trace(A @ A) # matrix product \r\nsum_sq = np.sum(A * A) # element-by-element product\r\nstable_rank = (tr_A ** 2) \/ tr_A2\r\n\r\nprint(f\"A =\\n{A}\\n\")\r\nprint(f\"rank(A)              = {rank_A}\")\r\nprint(f\"tr(A)                = {tr_A:.12f}\")\r\nprint(f\"tr(A^2) direct       = {tr_A2:.12f}\")\r\nprint(f\"tr(A^2) indirect     = {sum_sq:.12f}\")\r\nprint(f\"stable rank          = {stable_rank:.12f}\")\r\n<\/pre>\n
The code above produces the output below.<\/p>\n
A =\r\n[[ 1.09945682  0.4899665   0.98901845  0.66983113 -1.35006341]\r\n [ 0.4899665   0.98531254  0.35067791  0.89757603 -0.72037507]\r\n [ 0.98901845  0.35067791  4.31233926  0.94556225 -0.54819048]\r\n [ 0.66983113  0.89757603  0.94556225  1.3494295  -1.33840786]\r\n [-1.35006341 -0.72037507 -0.54819048 -1.33840786  3.54858332]]\r\n\r\nrank(A)              = 5\r\ntr(A)                = 11.295121449420\r\ntr(A^2) direct       = 51.035447533673\r\ntr(A^2) indirect     = 51.035447533673\r\nstable rank          = 2.499826585688\r\n<\/pre>\n
[1] Topological argument: A map from a connected space (such as \u211dn<\/em>\u00d7n<\/em><\/sup>) onto a discrete space (such as \u2124) cannot be continuous, otherwise the inverse images of the points in the range would partition the connected space into disjoint open sets, violating the definition of a connected space.<\/p>\n","protected":false},"excerpt":{"rendered":"
Suppose you want to know the rank of an n \u00d7 n matrix A, the number of linearly independent rows of\u00a0A, or equivalently the number of linearly independent columns. There are at least three difficulties. Difficulties in computing rank First of all, rank is not a continuous function of a matrix. Since rank is an […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[5,9],"tags":[198],"class_list":["post-247851","post","type-post","status-publish","format-standard","hentry","category-computing","category-math","tag-linear-algebra"],"acf":[],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\n","aioseo_head_json":{"title":"Computing a lower bound on matrix rank","description":"Why computing the rank of a matrix can be difficult and how the rank-trace inequality lower bound solves the difficulties if a lower bound is adequate.","canonical_url":"https:\/\/www.johndcook.com\/blog\/2026\/09\/04\/stable-rank\/","robots":"max-image-preview:large","keywords":"linear algebra","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"en_US","og:site_name":"John D. Cook | Applied Mathematics Consulting","og:type":"article","og:title":"Computing a lower bound on matrix rank","og:description":"Why computing the rank of a matrix can be difficult and how the rank-trace inequality lower bound solves the difficulties if a lower bound is adequate.","og:url":"https:\/\/www.johndcook.com\/blog\/2026\/09\/04\/stable-rank\/","article:published_time":"2026-09-04T14:16:16+00:00","article:modified_time":"2026-09-04T14:20:10+00:00","twitter:card":"summary","twitter:title":"Computing a lower bound on matrix rank","twitter:description":"Why computing the rank of a matrix can be difficult and how the rank-trace inequality lower bound solves the difficulties if a lower bound is adequate.","twitter:image":"https:\/\/www.johndcook.com\/blog\/wp-content\/uploads\/2022\/05\/twittercard.png"},"aioseo_meta_data":{"post_id":"247851","title":null,"description":"Why computing the rank of a matrix can be difficult and how the rank-trace inequality lower bound solves the difficulties if a lower bound is adequate.","keywords":null,"keyphrases":{"focus":{"keyphrase":"","score":0,"analysis":{"keyphraseInTitle":{"score":0,"maxScore":9,"error":1}}},"additional":[]},"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":"","og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"Article","isEnabled":true},"graphs":[]},"schema_type":"default","schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":"-1","robots_max_videopreview":"-1","robots_max_imagepreview":"large","priority":null,"frequency":"default","location":null,"local_seo":null,"breadcrumb_settings":null,"limit_modified_date":false,"created":"2026-09-04 13:08:46","updated":"2026-09-04 14:41:01","ai":{"faqs":[],"keyPoints":[],"schemas":[],"titles":[],"descriptions":[],"socialPosts":{"email":{"subject":"","preview":"","content":""},"linkedin":[],"twitter":[],"facebook":[],"instagram":[]}},"seo_analyzer_scan_date":null,"focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"aioseo_breadcrumb":"
\n\t\t\tHome<\/a>\n\t\t<\/span>»<\/span>\n\t\t\tComputing<\/a>\n\t\t<\/span>»<\/span>\n\t\t\tComputing a lower bound on matrix rank\n\t\t<\/span><\/div>","aioseo_breadcrumb_json":[{"label":"Home","link":"https:\/\/www.johndcook.com\/blog"},{"label":"Computing","link":"https:\/\/www.johndcook.com\/blog\/category\/computing\/"},{"label":"Computing a lower bound on matrix rank","link":"https:\/\/www.johndcook.com\/blog\/2026\/09\/04\/stable-rank\/"}],"_links":{"self":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/247851","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/comments?post=247851"}],"version-history":[{"count":5,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/247851\/revisions"}],"predecessor-version":[{"id":247856,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/247851\/revisions\/247856"}],"wp:attachment":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/media?parent=247851"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/categories?post=247851"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/tags?post=247851"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}},{"id":247847,"date":"2026-09-03T18:34:41","date_gmt":"2026-09-03T23:34:41","guid":{"rendered":"https:\/\/www.johndcook.com\/blog\/?p=247847"},"modified":"2026-09-04T06:01:12","modified_gmt":"2026-09-04T11:01:12","slug":"hugging-face-easter-egg","status":"publish","type":"post","link":"https:\/\/www.johndcook.com\/blog\/2026\/09\/03\/hugging-face-easter-egg\/","title":{"rendered":"Hugging Face Easter Egg"},"content":{"rendered":"
NVIDIA has offered to buy Hugging Face for $12,930,300,000.<\/p>\n
129303 is the Unicode code point for the Hugging Face emoj (U+1F917), which you can verify with the following Python code.<\/p>\n
\r\n>>> import unicodedata\r\n>>> 129303 == 0x1F917\r\nTrue\r\n>>> unicodedata.name(chr(0x1F917))\r\n'HUGGING FACE'\r\n<\/pre>\n
\"Hugging<\/p>\n
Related posts<\/h2>\n