21

Étant donné une matrice d'entiers, testez si elle est de rang un, ce qui signifie que chaque ligne est un multiple du même vecteur. Par exemple, dans

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

chaque ligne est un multiple de 1 0 -10 5.

La même définition fonctionne également avec des colonnes à la place des lignes. Alternativement, une matrice est de premier rang si elle ressemble à une table de multiplication:

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

Nous avons attribué des étiquettes de ligne r[i]et des étiquettes de colonne c[j]afin que chaque entrée de matrice M[i][j]soit le produit des étiquettes correspondantes en tant que M[i][j] = r[i] * c[j].

Contribution:

Une matrice entière comme conteneur 2D de votre choix. Par exemple, une liste de listes, un tableau 2D ou similaire. Vous ne devez pas prendre la largeur ou la hauteur comme entrées supplémentaires, sauf si le format du tableau l'exige.

La matrice peut être non carrée. Il aura au moins une entrée différente de zéro - vous n'avez pas à gérer des matrices vides ou nulles.

Vous pouvez supposer que les entiers ne causeront pas de problèmes de débordement.

Sortie:

Une valeur cohérente pour les matrices de rang 1 et une valeur cohérente différente pour les autres matrices.

Intégrés:

Vous ne pouvez pas utiliser de fonction intégrée pour calculer le rang ou vérifier directement le rang un. Vous pouvez utiliser d'autres valeurs intégrées comme les valeurs propres, les décompositions, etc., mais j'encourage les réponses de vote ascendant qui n'ont pas de valeurs intégrées font la plupart du travail.

Cas de test:

Rang un:

[[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]]

Pas le premier:

[[-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]]

Classement:

Afficher l'extrait de code

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>

Développer l'extrait

code-golf decision-problem matrix linear-algebra xnor
la source

2

Pour les curieux, une réponse Mathematica utilisant des fonctions intégrées ressemblerait à ceci (16 octets):MatrixRank@#==1&

JungHwan Min

Connexes

miles

2

Un beau théorème est que le rang des colonnes est égal au rang des lignes pour les matrices de dimension finie.

Leaky Nun

3

Avons-nous à nous soucier des problèmes de précision du flotteur? Ils peuvent faire apparaître une matrice de rang 1 comme rang 2 par exemple

Luis Mendo

@LuisMendo Vous devez gérer des problèmes de précision comme des valeurs propres de 1,0000000001, mais vous pouvez supposer que la matrice n'est pas grande et n'est pas spécifiquement choisie pour être mal classée.

xnor

13

Gelée , 6 octets

ẸÐfÆrE

Essayez-le en ligne!

Comment ça marche

ẸÐ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.

Précision

Ærutilise des méthodes numériques, donc ses résultats sont généralement inexacts. Par exemple, l'entrée [6, -5, 1] , qui représente le polynôme 6 - 5x + x² , donne les racines 3.0000000000000004 et 1.9999999999999998 . Cependant, la multiplication de tous les coefficients d'un polynôme par la même constante non nulle entraîne des racines également inexactes. Par exemple, Ærobtient les mêmes racines pour [6, -5, 1] et [6 × 10 ¹⁰⁰ , -5 × 10 ¹⁰⁰ , 10 ¹⁰⁰ ] .

Il convient de noter que la précision limitée des types flottants et complexes peut entraîner des erreurs. Par exemple, Ærobtiendrait les mêmes racines pour [1, 1] et [10 ¹⁰⁰ , 10 ¹⁰⁰ + 1] . Puisque nous pouvons supposer que la matrice n'est pas grande et n'est pas spécifiquement choisie pour être mal classée , cela devrait être bien.

Dennis
la source

5

multiplier tous les coefficients d'un polynôme par la même constante non nulle donne des racines également inexactes C'est une approche brillante

Luis Mendo

8

Haskell , 50 octets

rprend une liste de listes de Integers et retourne Falsesi la matrice a le rang un, Truesinon.

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

Essayez-le en ligne!

Comment ça marche

Génère toutes les paires de lignes aet b(y compris les lignes égales), et pour chaque paire, permet xet yexécute les éléments correspondants.
Multiplie la ligne bpar xet la ligne apar y. La matrice aura un rang si et seulement si les résultats sont toujours égaux.
Comme les paires sont générées dans les deux ordres, elles <peuvent être utilisées pour vérifier s'il y a jamais une inégalité. La liste des résultats des tests est combinée avec or, indiquant Trues'il y a des lignes non proportionnelles.

Ørjan Johansen
la source

7

Mathematica, 51 33 octets

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

Contribution

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

-14 octets de user202729
3 octets supplémentaires enregistrés à partir de junghwanmin

J42161217
la source

Je suggère qu'au lieu de construire une table avec une longueur égale à celle de First@#, vous pouvez calculer 0First@#puisque 0 multiplie avec tout est 0 et que la multiplication est listable. Vous pouvez également envisager d'utiliser Tr[1^<list>]pour calculer la longueur d'une liste.

user202729

très agréable. Je vais éditer!

J42161217

Au lieu de 0#&@@#, {0..}cela fonctionnerait aussi. Et puis Infixfonctionne, donc le code final pourrait être RowReduce@#~Count~{0..}==Tr[1^#]-1&, en économisant 2 octets.

JungHwan Min

En fait, Exceptpeut être utilisé pour se débarrasser de Trchoses. -3 octets:RowReduce@#~Count~Except@{0..}==1&

JungHwan Min

Je pense que la matrice à lignes réduites est garantie d'être non nulle (car la matrice d'origine est non nulle), donc le résultat du comptage sera un entier positif, donc <2peut être utilisé à la place de ==1.

user202729

4

JavaScript (ES6), 68 67 65 octets

Celui-ci est basé sur la réponse 05AB1E de Neil et est nettement plus efficace que mon approche d'origine.

Retourne falsepour le rang un et trueautrement.

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

Cas de test

Afficher l'extrait de code

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]]))

Développer l'extrait

Réponse originale, 84 octets

Retourne falsepour le rang un et trueautrement.

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

Cas de test

Afficher l'extrait de code

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]]))

Développer l'extrait

Comment?

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()

La soustraction qui est effectuée à la fin du code peut conduire à de nombreuses situations différentes, qui sont résumées ci-dessous:

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

Le test échoue dès que nous obtenons une valeur de truthy: cela se produit lorsque nous rencontrons deux rapports distincts (autres que 0/0 ) entre un (i, y) et un (i, r) dans une ligne y de la matrice, où r est l'indice d'une ligne non nulle.

Arnauld
la source

Huh, je me demandais juste moi-même ...

Neil

@Neil Souhaitez-vous l'afficher en tant que nouvelle réponse? Faites le moi savoir.

Arnauld

3

Python 2 + numpy, 58 octets

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

Essayez-le en ligne!

C'est le mérite de cela .

totalement humain
la source

Peut-on utiliser à la 1e-9place de 1e-10?

Jonathan Frech du

3

Gelée , 12 octets

ẸÐfµ÷"Ð€ZE€Ẹ

Essayez-le en ligne!

Explication

ẸÐ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?

L'explication peut être légèrement incorrecte car il s'agit de mon interprétation du golf de miles de mon algorithme d'origine

-5 octets grâce aux miles

HyperNeutrino
la source

... Votre code est accro à l'argent. (Je deviens déjà vu ...)

totalement humain

@icrieverytim Hé au moins le nombre de signes dollar est moins de la moitié de la longueur du code cette fois! : P

HyperNeutrino

1

@icrieverytim a corrigé un bug et maintenant encore moins de signes dollar: P

HyperNeutrino

Je crois que cela devrait aussi fonctionner pour 12 octets ẸÐfµ÷"Ð€ZE€Ẹ TIO

miles

@miles Oh sympa! L'approche pour la vôtre est un peu différente (je pense?) Donc vous pouvez poster cela comme votre propre réponse si vous le souhaitez :)

HyperNeutrino

3

05AB1E , 16 octets

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

Essayez-le en ligne! Utilise la propriété de table de multiplication selon laquelle les coins opposés de n'importe quel rectangle ont le même produit. Explication:

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

Neil
la source

3

TI-Basic (série TI-83), 28 27 28 octets (62 caractères)

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

Calcule la forme échelon ligne de la matrice [A], stocke sa première ligne (à supprimer) dans L₁et sa deuxième ligne dans ᶫX. Il max(abs(ᶫXsera alors nul si se ᶫXcompose uniquement de zéros et d'une valeur positive dans le cas contraire, qui not(passe à 1 si la matrice est de rang un, 0 sinon.

Pour une matrice à 1 ligne, ᶫXest défini sur {0}puis ne change pas lorsque nous essayons de regarder la deuxième ligne inexistante de la matrice.

-1 octet grâce à Scott Milner

+1 octet pour corriger l'erreur de dimension pour les matrices à 1 ligne. Il s'avère que la Matr►list( commande se plaint si vous essayez d'extraire la deuxième ligne d'une matrice avec une seule ligne; cependant, si vous essayez d'extraire les première et deuxième lignes de la matrice, cela échouera en silence.

Misha Lavrov
la source

1

Vous pouvez enregistrer un octet avec Prompt [A]au lieu de Ans→[A].

Scott Milner

@ScottMilner Merci! Il y a probablement un moyen d'éviter cela si nous utilisons quelque chose comme ClrListpour initialiser ᶫX, mais je n'ai pas tout à fait réussi à travailler dans moins d'espace.

Misha Lavrov

Débarrassez-vous de la deuxième ligne, car Matr►list(va écraser la liste, même si elle n'existe pas, et vous économiserez 5 octets.

kamoroso94

1

@ kamoroso94 Le point de la deuxième ligne n'est pas de créer une liste quand elle n'existe pas: le point de la deuxième ligne est de créer une valeur par défaut pour la deuxième ligne lorsque la matrice n'a qu'une seule ligne. Si vous vous débarrassez de la deuxième ligne, le code plante pour les matrices 1xN.

Misha Lavrov

2

@ kamoroso94 Il faudrait remplacer L1 par ᶫY, pas Y; sinon, la calculatrice pensera "extraire la Y-ème ligne de la matrice à ᶫX", pas "extraire la première ligne à ᶫY et la deuxième ligne à ᶫX".

Misha Lavrov

3

Brachylog , 27 octets

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

Essayez-le en ligne!

Utilise l'approche de Neil selon laquelle "les produits des coins opposés de chaque rectangle doivent être égaux". Le produit croisé est coûteux et prend 10 octets entiers, mais c'est toujours plus court que n'importe quelle approche basée sur la division que j'ai essayée, principalement en raison de la stipulation de deux sorties cohérentes pour truey et falsey dans la question - faire de falsey seulement un false., et pas parfois un erreur de division par zéro, utilise trop d'octets.

{⊇Ċ}ᶠ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.)

Approche alternative basée sur la division par élément ( 30 octets ):

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

Essayez-le en ligne!

Sundar - Rétablir Monica
la source

2

Gelée , 9 octets

ẸÐf÷g/$€E

Essayez-le en ligne!

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

Lynn
la source

1

SageMath, 40 octets

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

Essayez-le en ligne

Cette fonction anonyme renvoie Falsesi la matrice est de premier rang, et Truesinon.

La fonction prend une matrice Men entrée, la convertit en forme d'échelon de ligne réduite ( M.rref()) et teste que anyles lignes après la première sont non nulles. Ensuite, cette valeur est multipliée par M.nrows()>1(la matrice a-t-elle plus d'une ligne?).

Mego
la source

1

Python 3 , 93 91 octets

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

Essayez-le en ligne!

Comment ça marche

Vérifie si un mineur de 2 a un déterminant non nul. Si tel est le cas, le rang doit être d'au moins 2: "Un p-mineur non disparaissant (sous-matrice p × p avec déterminant non nul) montre que les lignes et les colonnes de cette sous-matrice sont linéairement indépendantes, et donc ces lignes et les colonnes de la matrice complète sont linéairement indépendantes (dans la matrice complète), de sorte que le rang des lignes et des colonnes est au moins aussi grand que le rang déterminant "(d'après Wikipedia )

Remarque: rasé de deux octets grâce au commentaire de user71546.

Luca Citi
la source

1

91 - plus court si vous mettez enumerate dans les arguments de la fonction et éliminez ainsi le besoin de 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))

Shieru Asakoto

@ user71546 Merci! C'est fait!

Luca Citi

0

Pari / GP , 18 octets

a->#matimage(a)==1

matimage donne une base à l'image de la transformation linéaire définie par la matrice.

Essayez-le en ligne!

alephalpha
la source

La matrice est-elle de premier rang?

Réponses:

Gelée , 6 octets

Comment ça marche

Précision

Haskell , 50 octets

Comment ça marche

Mathematica, 51 33 octets

JavaScript (ES6), 68 67 65 octets

Cas de test

Réponse originale, 84 octets

Cas de test

Comment?

Python 2 + numpy, 58 octets

Gelée , 12 octets

Explication

05AB1E , 16 octets

TI-Basic (série TI-83), 28 27 28 octets (62 caractères)

Brachylog , 27 octets

Gelée , 9 octets

SageMath, 40 octets

Python 3 , 93 91 octets

Pari / GP , 18 octets