21
\$\begingroup\$

Given a matrix of integers, test if it's rank-one, meaning that every row is a multiple of the same vector. For example, in

 2   0  -20  10  
-3   0   30 -15
 0   0   0   0

every row is a multiple of 1 0 -10 5.

The same definition also works with columns in place of rows. Alternatively, a matrix is rank-one if it's like a multiplication table:

 *    1   0  -10  5
    ----------------
 2 |  2   0  -20  10  
-3 | -3   0   30 -15
 0 |  0   0   0   0

We've assigned row labels r[i]and column labels c[j] so that each matrix entry M[i][j] is the product of the corresponding labels as M[i][j] = r[i] * c[j].

Input:

An integer matrix as a 2D container of your choice. For example, a list of lists, a 2D array, or similar. You shouldn't take the width or height as additional inputs unless the array format requires it.

The matrix may be non-square. It will have at least one nonzero entry -- you don't have to deal with empty or zero matrices.

You can assume the integers won't cause overflow issues.

Output:

A consistent value for rank-one matrices, and a different consistent value for other matrices.

Built-ins:

You may not use any built-in to computes rank or directly check rank one. You may use other built-ins like eigenvalues, decompositions, etc, but I encourage upvoting answers that don't have built-ins do most of the work.

Test cases:

Rank-one:

[[2, 0, -20, 10], [-3, 0, 30, -15], [0, 0, 0, 0]]
[[0, 0, 0], [0, 3, 0], [0, 0, 0]]
[[-10]]
[[0, 0, 0], [0, 4, 11], [0, -4, -11]]

Not rank-one:

[[-2, 1], [2, 4]]
[[0, 0, 3], [-22, 0, 0]]
[[1, 2, 3], [2, 4, 6], [3, 6, 10]]
[[0, -2, 0, 0], [0, 0, 0, 1], [0, 0, -2, 0]]

Leaderboard:

var QUESTION_ID=143528,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/143528/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

\$\endgroup\$
  • 2
    \$\begingroup\$ For the curious, a Mathematica response using builtins would look like this (16 bytes): MatrixRank@#==1& \$\endgroup\$ – JungHwan Min Sep 23 '17 at 1:22
  • \$\begingroup\$ Related \$\endgroup\$ – miles Sep 23 '17 at 1:27
  • 2
    \$\begingroup\$ A beautiful theorem is that column rank is equal to row rank for finite dimensional matrices. \$\endgroup\$ – Leaky Nun Sep 23 '17 at 6:30
  • 3
    \$\begingroup\$ Do we have to worry about float precision issues? They may make a rank-1 matrix seem rank 2 for instance \$\endgroup\$ – Luis Mendo Sep 23 '17 at 10:11
  • \$\begingroup\$ @LuisMendo You do have to handle precision issues like an eigenvalues of 1.0000000001, but can assume the matrix is not large and not specifically chosen to be misclassified. \$\endgroup\$ – xnor Sep 23 '17 at 14:33

13 Answers 13

12
\$\begingroup\$

Jelly, 6 bytes

ẸÐfÆrE

Try it online!

How it works

ẸÐfÆrE  Main link. Argument: M (2D array)

ẸÐf     Filter by any, removing rows of zeroes.
   Ær   Interpret each row as coefficients of a polynomial and solve it over the
        complex numbers.
     E  Test if all results are equal.

Precision

Ær uses numerical methods, so its results are usually inexact. For example, the input [6, -5, 1], which represents the polynomial 6 - 5x + x², results in the roots 3.0000000000000004 and 1.9999999999999998. However, multiplying all coefficients of a polynomial by the same non-zero constant results in equally inexact roots. For example, Ær obtains the same roots for [6, -5, 1] and [6 × 10100, -5 × 10100, 10100].

It should be noted that the limited precision of the float and complex types can lead to errors. For example, Ær would obtain the same roots for [1, 1] and [10100, 10100 + 1]. Since we can assume the matrix is not large and not specifically chosen to be misclassified, that should be fine.

\$\endgroup\$
  • 5
    \$\begingroup\$ multiplying all coefficients of a polynomial by the same non-zero constant results in equally inexact roots That's a brilliant approach \$\endgroup\$ – Luis Mendo Sep 23 '17 at 16:27
8
\$\begingroup\$

Haskell, 50 bytes

r takes a list of lists of Integers and returns False if the matrix has rank one, True otherwise.

r l=or[map(x*)b<map(y*)a|a<-l,b<-l,(x,y)<-zip a b]

Try it online!

How it works

  • Generates all pairs of rows a and b (including equal rows), and for each pair, lets x and y run through corresponding elements.
  • Multiplies the row b by x and the row a by y. The matrix will have rank one if and only if the results are always equal.
  • Since pairs are generated in both orders, < can be used to check if there's ever an inequality. The list of test results are combined with or, giving True if there are any non-proportional rows.
\$\endgroup\$
7
\$\begingroup\$

Mathematica, 51 33 bytes

RowReduce@#~Count~Except@{0..}<2&

Input

[{{2,0,-20,10},{-3,0,30,-15},{0,0,0,0}}]

-14 bytes from user202729
3 more bytes saved from junghwanmin

\$\endgroup\$
  • \$\begingroup\$ I suggest that, instead of construct a table with length equal to that of First@#, you can calculate 0First@# since 0 multiplies with everything is 0, and multiplication is listable. Also you may consider using Tr[1^<list>] to calculate the length of a list. \$\endgroup\$ – user202729 Sep 23 '17 at 2:43
  • \$\begingroup\$ very nice.I'll edit! \$\endgroup\$ – J42161217 Sep 23 '17 at 2:46
  • \$\begingroup\$ Instead of 0#&@@#, {0..} would work too. And then Infix works, so the final code could be RowReduce@#~Count~{0..}==Tr[1^#]-1&, saving 2 bytes. \$\endgroup\$ – JungHwan Min Sep 23 '17 at 4:26
  • \$\begingroup\$ Actually, Except can be used to get rid of Tr stuff. -3 bytes: RowReduce@#~Count~Except@{0..}==1& \$\endgroup\$ – JungHwan Min Sep 23 '17 at 4:31
  • \$\begingroup\$ I think the row-reduced matrix is guaranteed to be nonzero (because the original matrix is nonzero), thus the count result will be an positive integer, thus <2 can be used instead of ==1. \$\endgroup\$ – user202729 Sep 23 '17 at 9:27
4
\$\begingroup\$

JavaScript (ES6), 68 67 65 bytes

This one is based on Neil's 05AB1E answer and is significantly more efficient than my original approach.

Returns false for rank-one and true otherwise.

f=(a,R,V,X)=>a.some(r=>r.some((v,x)=>R?v*V-r[X]*R[x]:f(a,r,v,x)))

Test cases

f=(a,R,V,X)=>a.some(r=>r.some((v,x)=>R?v*V-r[X]*R[x]:f(a,r,v,x)))

console.log(f([[2, 0, -20, 10], [-3, 0, 30, -15], [0, 0, 0, 0]]))
console.log(f([[0, 0, 0], [0, 3, 0], [0, 0, 0]]))
console.log(f([[-10]]))
console.log(f([[0, 0, 0], [0, 4, 11], [0, -4, -11]]))

console.log(f([[-2, 1], [2, 4]]))
console.log(f([[0, 0, 3], [-22, 0, 0]]))
console.log(f([[1, 2, 3], [2, 4, 6], [3, 6, 10]]))
console.log(f([[0, -2, 0, 0], [0, 0, 0, 1], [0, 0, -2, 0]]))


Original answer, 84 bytes

Returns false for rank-one and true otherwise.

a=>a.some(r=>r.some((x,i)=>(isNaN(x/=a.find(r=>r.some(x=>x))[i])?r:1/r[0]?r=x:x)-r))

Test cases

let f =

a=>a.some(r=>r.some((x,i)=>(isNaN(x/=a.find(r=>r.some(x=>x))[i])?r:1/r[0]?r=x:x)-r))

console.log(f([[2, 0, -20, 10], [-3, 0, 30, -15], [0, 0, 0, 0]]))
console.log(f([[0, 0, 0], [0, 3, 0], [0, 0, 0]]))
console.log(f([[-10]]))
console.log(f([[0, 0, 0], [0, 4, 11], [0, -4, -11]]))

console.log(f([[-2, 1], [2, 4]]))
console.log(f([[0, 0, 3], [-22, 0, 0]]))
console.log(f([[1, 2, 3], [2, 4, 6], [3, 6, 10]]))
console.log(f([[0, -2, 0, 0], [0, 0, 0, 1], [0, 0, -2, 0]]))

How?

a => a.some(r =>          // given a matrix a, for each row r of a:
  r.some((x, i) =>        //   for each value x of r at position i:
    (                     //
      isNaN(x /=          //     divide x by a[ref][i]
        a.find(r =>       //       where ref is the index of the first row that
          r.some(x => x)  //       contains at least one non-zero value
        )[i]              //       (guaranteed to exist by challenge rules)
      ) ?                 //     we get NaN for 0/0, in which case:
        r                 //       use r, so that this column is ignored
      :                   //     else:
        1 / r[0] ?        //       if r is still holding the current row:
          r = x           //         set it to x (either a float, +Inf or -Inf)
        :                 //       else:
          x               //         use x
    ) - r                 //     subtract r from the value set above (see table)
  )                       //   end of some()
)                         // end of every()

The subtraction which is performed at the end of the code can lead to many different situations, which are summarized below:

A                   | B              | A - B       | False / True
--------------------+----------------+-------------+-------------
array of 1 number   | same array     | 0           | False
array of 2+ numbers | same array     | NaN         | False
a number            | same number    | 0           | False
+Infinity           | +Infinity      | NaN         | False
-Infinity           | -Infinity      | NaN         | False
a number            | another number | <> 0        | True
+Infinity           | -Infinity      | +Infinity   | True
-Infinity           | +Infinity      | -Infinity   | True
a number            | +/-Infinity    | +/-Infinity | True
+/-Infinity         | a number       | +/-Infinity | True

The test fails as soon as we get a truthy value: this happens when we encounter two distinct ratios (other than 0 / 0) between a(i,y) and a(i,r) in any row y of the matrix, where r is the index of a non-zero row.

\$\endgroup\$
  • \$\begingroup\$ Huh, I was just wondering that myself... \$\endgroup\$ – Neil Sep 23 '17 at 11:58
  • \$\begingroup\$ @Neil Would you like to post it as a new answer? Just let me know. \$\endgroup\$ – Arnauld Sep 23 '17 at 12:01
3
\$\begingroup\$

Python 2 + numpy, 58 bytes

lambda m:sum(linalg.svd(m)[1]>1e-10)==1
from numpy import*

Try it online!

Credit to this.

\$\endgroup\$
  • \$\begingroup\$ Could one use 1e-9 instead of 1e-10? \$\endgroup\$ – Jonathan Frech Oct 12 '17 at 21:27
3
\$\begingroup\$

Jelly, 12 bytes

ẸÐfµ÷"ЀZE€Ẹ

Try it online!

Explanation

ẸÐfµ÷"ЀZE€Ẹ  Main link
 Ðf           Filter; keep all elements where
Ẹ             At least one element is truthy (remove zero-rows)
      Ѐ      For each row on the right side
    ÷"        Divide it by each row in the original
        Z     Zip the array
          €   For each submatrix
         E    Are all rows equal?
           Ẹ  Is at least one of the elements from above truthy?

Explanation may be slightly incorrect as this is my interpretation of miles's golf of my original algorithm

-5 bytes thanks to miles

\$\endgroup\$
  • \$\begingroup\$ ...Your code is addicted to money. (I'm getting deja vu...) \$\endgroup\$ – totallyhuman Sep 23 '17 at 2:23
  • \$\begingroup\$ @icrieverytim Hey at least the number of dollar signs is less than half of the length of the code this time! :P \$\endgroup\$ – HyperNeutrino Sep 23 '17 at 2:25
  • 1
    \$\begingroup\$ @icrieverytim fixed a bug and now even fewer dollar signs :P \$\endgroup\$ – HyperNeutrino Sep 23 '17 at 2:35
  • \$\begingroup\$ I believe this should work too for 12 bytes ẸÐfµ÷"ЀZE€Ẹ TIO \$\endgroup\$ – miles Sep 23 '17 at 3:04
  • \$\begingroup\$ @miles Oh nice! The approach for yours is a bit different (I think?) so you can post that as your own answer of you'd like :) \$\endgroup\$ – HyperNeutrino Sep 23 '17 at 3:06
3
\$\begingroup\$

05AB1E, 16 bytes

2ãεø2ãε`R*`Q}W}W

Try it online! Uses the multiplication table property that the opposite corners of any rectangle have the same product. Explanation:

2ãε           }     Loop over each pair of rows
   ø                Transpose the pair into a row of pairs
    2ãε     }       Loop over each pair of columns
       `R*`Q        Cross-multiply and check for equality
             W W    All results must be true
\$\endgroup\$
3
\$\begingroup\$

TI-Basic (TI-83 series), 28 27 28 bytes (62 characters)

:Prompt [A]
:{0→X
:Matr►list(ref([A])ᵀ,L₁,X
:not(max(abs(ᶫX

Computes the row-echelon form of the matrix [A], stores its first row (to be discarded) in L₁ and its second row in ᶫX. Then max(abs(ᶫX will be zero if ᶫX consists only of zeroes, and a positive value otherwise, which not( changes to 1 if the matrix is rank one, 0 otherwise.

For a 1-row matrix, ᶫX is set to {0} and then doesn't get changed when we try to look at the nonexistent second row of the matrix.


-1 byte thanks to Scott Milner

+1 byte to fix dimension error for 1-row matrices. Turns out the Matr►list( command complains if you try to extract the second row from a matrix with only one row; however, if you try to extract the first and second row both from the matrix, it will fail silently.

\$\endgroup\$
  • 1
    \$\begingroup\$ You can save a byte with Prompt [A] instead of Ans→[A]. \$\endgroup\$ – Scott Milner Sep 23 '17 at 18:22
  • \$\begingroup\$ @ScottMilner Thanks! There's probably a way to avoid either if we use something like ClrList to initialize ᶫX, but I haven't quite gotten that to work in less space. \$\endgroup\$ – Misha Lavrov Sep 23 '17 at 19:08
  • \$\begingroup\$ Get rid of the second line, since Matr►list( will overwrite the list, even if it doesn't exist, and you'll save 5 bytes. \$\endgroup\$ – kamoroso94 Sep 23 '17 at 20:59
  • 1
    \$\begingroup\$ @kamoroso94 The point of the second line is not to create a list when it doesn't exist: the point of the second line is to create a default value for the second row when the matrix only has one row. If you get rid of the second line, the code crashes for 1xN matrices. \$\endgroup\$ – Misha Lavrov Sep 23 '17 at 21:02
  • 2
    \$\begingroup\$ @kamoroso94 We'd have to replace L1 with ᶫY, not Y; otherwise, the calculator will think "extract the Y-th row of the matrix to ᶫX", not "extract the first row to ᶫY, and the second row to ᶫX". \$\endgroup\$ – Misha Lavrov Sep 23 '17 at 21:06
3
\$\begingroup\$

Brachylog, 27 bytes

{⊇Ċ}ᶠzᵐ{↰₁ᶠ{⟨hz{t↔}⟩×ᵐ=}ᵐ}ᵐ

Try it online!

Uses Neil's approach of "products of opposite corners of each rectangle should be equal". Cross product is costly and takes 10 whole bytes, but this is still shorter than any division based approach I tried, mainly because of the stipulation of two consistent outputs for truthy and falsey in the question - making falsey be only a false., and not sometimes a divide-by-zero error, uses too many bytes.

{⊇Ċ}ᶠzᵐ{↰₁ᶠ{⟨hz{t↔}⟩×ᵐ=}ᵐ}ᵐ
{⊇Ċ}ᶠ                        Get each pair of rows from the matrix
                             eg.: [ [[a, b, c], [k, l, m]], ... ]
     zᵐ                      Zip each pair's elements
                                  [ [[a, k], [b, l], [c, m]], ... ]
       {                 }ᵐ  Map this over each pair of rows:
                                  [[a, k], [b, l], [c, m]]
        ↰₁ᶠ                  Get each pair of paired elements from the rows
                                  [[[a, k], [b, l]], [[b, l], [c, m]], [[a, k], [c, m]]]
           {           }ᵐ    Map this over each pair of pairs
                                  [[a, k], [b, l]]
            ⟨hz{t↔}⟩         Zip the first pair with the reverse of the second
                                  [[a, l], [k, b]]
                    ×ᵐ       Multiply within each sublist
                                  [al, kb]
                      =      The results should be equal
                             (If the results are unequal for any pair, the whole predicate fails,
                              and outputs false.)

Alternate approach based on element-wise division (30 bytes):

{≡ᵉ¬0&}ˢ\↰₁ˢ{c׬0&⟨hz∋⟩ᶠ/ᵐ²=ᵐ}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Jelly, 9 bytes

ẸÐf÷g/$€E

Try it online!

ẸÐf         Discard zero rows
   ÷  $€    Divide each row by
    g/        its greatest common divisor
        E   Does this list have only one unique element?
\$\endgroup\$
1
\$\begingroup\$

SageMath, 40 bytes

lambda M:any(M.rref()[1:])*(M.nrows()>1)

Try it online

This anonymous function returns False if the matrix is rank-one, and True otherwise.

The function takes a matrix M as input, converts it to reduced row-echelon form (M.rref()), and tests for any of the rows past the first being non-zero. Then, that value is multiplied by M.nrows()>1 (does the matrix have more than one row?).

\$\endgroup\$
1
\$\begingroup\$

Python 3, 93 91 bytes

lambda m,e=enumerate:any(h*g-r[j]*s[i]for r in m for i,h in e(r)for s in m for j,g in e(s))

Try it online!

How it works

Checks if any 2-minor has nonzero determinant. If this is the case the rank must be at least 2: "A non-vanishing p-minor (p × p submatrix with non-zero determinant) shows that the rows and columns of that submatrix are linearly independent, and thus those rows and columns of the full matrix are linearly independent (in the full matrix), so the row and column rank are at least as large as the determinantal rank" (from Wikipedia)

Note: shaved two bytes thanks to user71546's comment.

\$\endgroup\$
  • 1
    \$\begingroup\$ 91 - shorter if putting enumerate into the function arguments and thus eliminating the need of f=: lambda m,e=enumerate:any(h*g-r[j]*s[i]for r in m for i,h in e(r)for s in m for j,g in e(s)) \$\endgroup\$ – Shieru Asakoto Aug 21 '18 at 2:14
  • \$\begingroup\$ @user71546 Thanks! Done it! \$\endgroup\$ – Luca Citi Aug 21 '18 at 15:38
0
\$\begingroup\$

Pari/GP, 18 bytes

a->#matimage(a)==1

matimage gives a basis of the image of the linear transformation defined by the matrix.

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.