Is the matrix rank-one?

Question

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>

Answer 1

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 × 10¹⁰⁰, -5 × 10¹⁰⁰, 10¹⁰⁰].

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 [10¹⁰⁰, 10¹⁰⁰ + 1]. Since we can assume the matrix is not large and not specifically chosen to be misclassified, that should be fine.

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

05AB1E, 16 13 bytes

2ãεø2ãε`R*E]W

Try it online! Uses the multiplication table property that the opposite corners of any rectangle have the same product. Edit: Saved 3 bytes thanks to @KevinCruijssen. Explanation:

2ãε             Loop over each pair of rows
   ø            Transpose the pair into a row of pairs
    2ãε         Loop over each pair of columns
       `R*E     Cross-multiply and check for equality
           ]W   All results must be true

Answer 6

Python 2 + numpy, 58 bytes

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

Try it online!

Credit to this.

Answer 7

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

Answer 8

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.

Answer 9

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!

Answer 10

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?

Answer 11

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?).

Answer 12

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.

Answer 13

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!

Answer 14

Scala, 86 bytes

Golfed version. Try it online!

l=>l.exists(a=>l.exists(b=>a.zip(b).exists{case(x,y)=>b.map(_*x).sum<a.map(_*y).sum}))

Ungolfed version. Try it online!

object Main extends App {
  val lists = List(
    List(List(2, 0, -20, 10), List(-3, 0, 30, -15), List(0, 0, 0, 0)),
    List(List(0, 0, 0), List(0, 3, 0), List(0, 0, 0)),
    List(List(-10)),
    List(List(0, 0, 0), List(0, 4, 11), List(0, -4, -11)),
    List(List(-2, 1), List(2, 4)),
    List(List(0, 0, 3), List(-22, 0, 0)),
    List(List(1, 2, 3), List(2, 4, 6), List(3, 6, 10)),
    List(List(0, -2, 0, 0), List(0, 0, 0, 1), List(0, 0, -2, 0))
  )
  
  lists.foreach { list =>
    println(s"$list: ${r(list)}")
  }

  def r(list: List[List[Int]]): Boolean = {
    list.exists { a =>
      list.exists { b =>
        a.zip(b).exists { case (x, y) =>
          b.map(_ * x).sum < a.map(_ * y).sum
        }
      }
    }
  }
}