Ist die Matrix der erste Rang?

21

Testen Sie anhand einer Ganzzahlmatrix, ob es sich um eine Rang-1-Matrix handelt. Dies bedeutet, dass jede Zeile ein Vielfaches desselben Vektors ist. Zum Beispiel in

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

Jede Zeile ist ein Vielfaches von 1 0 -10 5.

Dieselbe Definition gilt auch für Spalten anstelle von Zeilen. Alternativ hat eine Matrix den ersten Rang, wenn es sich um eine Multiplikationstabelle handelt:

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

Wir haben Zeilenbeschriftungen r[i]und Spaltenbeschriftungen zugewiesen , c[j]sodass jeder Matrixeintrag M[i][j]das Produkt der entsprechenden Beschriftungen als ist M[i][j] = r[i] * c[j].

Eingang:

Eine ganzzahlige Matrix als 2D-Container Ihrer Wahl. Zum Beispiel eine Liste von Listen, ein 2D-Array oder ähnliches. Sie sollten die Breite oder Höhe nicht als zusätzliche Eingabe verwenden, es sei denn, das Array-Format erfordert dies.

Die Matrix kann nicht quadratisch sein. Es wird mindestens einen Eintrag ungleich Null haben - Sie müssen sich nicht mit leeren oder Null-Matrizen befassen.

Sie können davon ausgehen, dass die Ganzzahlen keine Überlaufprobleme verursachen.

Ausgabe:

Ein konsistenter Wert für Rang-1-Matrizen und ein anderer konsistenter Wert für andere Matrizen.

Eingebaute:

Sie dürfen keine eingebauten Funktionen verwenden, um Rang 1 zu berechnen oder direkt zu überprüfen. Sie können auch andere integrierte Funktionen wie Eigenwerte, Zerlegungen usw. verwenden. Ich empfehle jedoch, Antworten zu wählen, für die die meisten Aufgaben nicht integriert sind.

Testfälle:

Rang eins:

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

Nicht Rang eins:

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

Bestenliste:

xnor
quelle
2
Für die Neugierigen würde eine Mathematica-Antwort mit eingebauten Elementen wie folgt aussehen (16 Byte):MatrixRank@#==1&
JungHwan Min
Related
Meilen
2
Ein schönes Theorem ist, dass der Spaltenrang dem Zeilenrang für endlich dimensionale Matrizen entspricht.
Undichte Nonne
3
Müssen wir uns um Probleme mit der Schwimmerpräzision sorgen? Sie lassen eine Matrix mit Rang 1 beispielsweise als Rang 2 erscheinen
Luis Mendo,
@LuisMendo Sie müssen Präzisionsprobleme wie einen Eigenwert von 1,0000000001 behandeln, können jedoch davon ausgehen, dass die Matrix nicht groß und nicht speziell für eine Fehlklassifizierung ausgewählt ist.
Xnor

Antworten:

13

Gelee , 6 Bytes

ẸÐfÆrE

Probieren Sie es online!

Wie es funktioniert

ẸÐ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äzision

Ærverwendet numerische Methoden, so dass die Ergebnisse in der Regel ungenau sind. Beispielsweise ergibt der Eingang [6, -5, 1] , der das Polynom 6 - 5x + x² darstellt , die Wurzeln 3.0000000000000004 und 1.99999999999998 . Das Multiplizieren aller Koeffizienten eines Polynoms mit derselben Nicht-Null-Konstante führt jedoch zu gleichermaßen ungenauen Wurzeln. Ermittelt zum Beispiel Ærdie gleichen Wurzeln für [6, -5, 1] und [6 × 10 100 , -5 × 10 100 , 10 100 ] .

Es sei darauf hingewiesen , dass die begrenzte Genauigkeit der Schwimmer und komplexen Typen können zu Fehlern führen. Zum Beispiel Ærwürde man die gleichen Wurzeln für [1, 1] und [10 100 , 10 100 + 1] erhalten . Da wir davon ausgehen können, dass die Matrix nicht groß und nicht speziell für eine Fehlklassifizierung ausgewählt ist, sollte dies in Ordnung sein.

Dennis
quelle
5
Das Multiplizieren aller Koeffizienten eines Polynoms mit derselben Nicht-Null-Konstante führt zu gleichermaßen ungenauen Wurzeln. Das ist ein brillanter Ansatz
Luis Mendo
8

Haskell , 50 Bytes

rNimmt eine Liste von Listen von Integers und gibt zurück, Falsewenn die Matrix Rang eins hat, Trueansonsten.

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

Probieren Sie es online!

Wie es funktioniert

  • Erzeugt alle Paare von Zeilen aund b(einschließlich der Gleich Zeilen), und für jedes Paar, läßt xund ylaufen durch entsprechende Elemente.
  • Multipliziert die Reihe bmit xund die Reihe amit y. Die Matrix hat genau dann den ersten Rang, wenn die Ergebnisse immer gleich sind.
  • Da Paare in beiden Reihenfolgen generiert werden, <kann damit geprüft werden, ob jemals eine Ungleichung vorliegt. Die Liste der Testergebnisse wird mit kombiniert orund gibt an, Trueob nicht proportionale Zeilen vorhanden sind.
Ørjan Johansen
quelle
7

Mathematica, 51 33 Bytes

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

Eingang

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

-14 bytes von user202729
3 weitere bytes von junghwanmin gespeichert

J42161217
quelle
Ich schlage vor, dass Sie anstelle der Erstellung einer Tabelle mit der Länge von First@#berechnen können, 0First@#da 0 mit 0 multipliziert wird und die Multiplikation auflistbar ist. Sie können auch in Betracht ziehen Tr[1^<list>], die Länge einer Liste mit zu berechnen.
user202729
sehr schön.Ich werde bearbeiten!
J42161217
Statt 0#&@@#, {0..}würde auch funktionieren. Und dann Infixfunktioniert es, also könnte der endgültige Code RowReduce@#~Count~{0..}==Tr[1^#]-1&2 Bytes einsparen.
JungHwan Min
Eigentlich Exceptkann verwendet werden, um TrSachen loszuwerden . -3 Bytes:RowReduce@#~Count~Except@{0..}==1&
JungHwan Min
Ich denke, die zeilenreduzierte Matrix ist garantiert ungleich Null (da die ursprüngliche Matrix ungleich Null ist), daher ist das Zählergebnis eine positive ganze Zahl und <2kann daher anstelle von verwendet werden ==1.
user202729
4

JavaScript (ES6), 68 67 65 Bytes

Dieser basiert auf Neils 05AB1E-Antwort und ist bedeutend effizienter als mein ursprünglicher Ansatz.

Gibt falsefür Rang eins und truesonst zurück.

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

Testfälle


Ursprüngliche Antwort, 84 Bytes

Gibt falsefür Rang eins und truesonst zurück.

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

Testfälle

Wie?

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

Die Subtraktion, die am Ende des Codes ausgeführt wird, kann zu vielen verschiedenen Situationen führen, die im Folgenden zusammengefasst sind:

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

Der Test fehlschlägt, sobald wir einen truthy Wert zu erhalten: dies geschieht , wenn wir begegnen zwei unterschiedliche Verhältnisse (ausgenommen 0/0 ) , die zwischen a (i, y) und a (i, r) in einem beliebigen Zeile y der Matrix, wobei r ist der Index einer Zeile ungleich Null.

Arnauld
quelle
Huh, ich habe mich nur gewundert, dass ich ...
Neil
@Neil Möchtest du es als neue Antwort posten? Lass es mich wissen.
Arnauld
3

Python 2 + Anzahl, 58 Bytes

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

Probieren Sie es online!

Gut so .

total menschlich
quelle
Könnte man 1e-9statt verwenden 1e-10?
Jonathan Frech
3

Gelee , 12 Bytes

ẸÐfµ÷"ЀZE€Ẹ

Probieren Sie es online!

Erläuterung

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

Die Erklärung ist möglicherweise etwas falsch, da dies meine Interpretation des Meilengolfs meines ursprünglichen Algorithmus ist

-5 Bytes dank Meilen

HyperNeutrino
quelle
... Ihr Code ist geldsüchtig. (Ich bekomme deja vu ...)
totalhuman
@icrieverytim Hey, zumindest die Anzahl der Dollarzeichen ist diesmal weniger als die Hälfte der Länge des Codes! : P
HyperNeutrino
1
@icrieverytim hat einen Fehler behoben und jetzt noch weniger Dollarzeichen: P
HyperNeutrino
Ich glaube, das sollte auch für 12 Bytes ẸÐfµ÷"ЀZE€Ẹ TIO
Meilen
@ Meilen Oh schön! Der Ansatz für Sie ist ein bisschen anders (glaube ich?), So dass Sie dies als Ihre eigene Antwort
posten können
3

05AB1E , 16 Bytes

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

Probieren Sie es online! Verwendet die Multiplikationstabelleneigenschaft, dass die gegenüberliegenden Ecken eines Rechtecks ​​dasselbe Produkt haben. Erläuterung:

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
quelle
3

TI-Basic (TI-83-Serie), 28 27 28 Byte (62 Zeichen)

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

Berechnet die Reihenform der Matrix [A], speichert die erste (zu verwerfende) Reihe L₁und die zweite Reihe in ᶫX. Dann max(abs(ᶫXist Null, wenn es ᶫXnur aus Nullen besteht, und ansonsten ein positiver Wert, der not(sich in 1 ändert, wenn die Matrix den Rang Eins hat, andernfalls 0.

Bei einer einzeiligen Matrix ᶫXwird festgelegt, dass {0}und wird dann nicht geändert, wenn versucht wird, die nicht vorhandene zweite Zeile der Matrix zu betrachten.


-1 Byte dank Scott Milner

+1 Byte, um den Dimensionsfehler für 1-Zeilen-Matrizen zu beheben. Der Matr►list( Befehl beschwert sich, wenn Sie versuchen, die zweite Zeile aus einer Matrix mit nur einer Zeile zu extrahieren. Wenn Sie jedoch versuchen, die erste und die zweite Zeile aus der Matrix zu extrahieren, schlägt dies unbemerkt fehl.

Mischa Lawrow
quelle
1
Sie können ein Byte mit Prompt [A]anstelle von speichern Ans→[A].
Scott Milner
@ScottMilner Danke! Es gibt wahrscheinlich einen Weg, dies zu vermeiden, wenn wir etwas wie ClrListInitialisieren verwenden ᶫX, aber ich habe es nicht ganz verstanden, um auf weniger Raum zu arbeiten.
Mischa Lawrow
Beseitigen Sie die zweite Zeile, da Matr►list(die Liste überschrieben wird, auch wenn sie nicht vorhanden ist, und Sie sparen 5 Bytes.
Kamoroso94
1
@ kamoroso94 Der Punkt der zweiten Zeile dient nicht zum Erstellen einer Liste, wenn sie nicht vorhanden ist. Der Punkt der zweiten Zeile dient zum Erstellen eines Standardwerts für die zweite Zeile, wenn die Matrix nur eine Zeile enthält. Wenn Sie die zweite Zeile loswerden, stürzt der Code für 1xN-Matrizen ab.
Mischa Lawrow
2
@ kamoroso94 Wir müssten L1 durch ᶫY ersetzen, nicht durch Y; Andernfalls denkt der Rechner "extrahiere die y-te Zeile der Matrix nach ᶫX", nicht "extrahiere die erste Zeile nach ᶫY und die zweite Zeile nach ᶫX".
Mischa Lawrow
3

Brachylog , 27 Bytes

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

Probieren Sie es online!

Verwendet Neils Ansatz "Produkte mit entgegengesetzten Ecken jedes Rechtecks ​​sollten gleich sein". Kreuzprodukt ist teuer und benötigt 10 ganze Bytes, aber dies ist immer noch kürzer als jeder divisionsbasierte Ansatz, den ich ausprobiert habe, hauptsächlich aufgrund der Vorgabe von zwei konsistenten Ausgaben für Wahrhaftigkeit und Falschheit in der Frage - Falschheit ist nur eine false., und nicht manchmal eine Fehler beim Teilen durch Null, verwendet zu viele 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.)

Alternativer Ansatz basierend auf elementweiser Aufteilung ( 30 Bytes ):

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

Probieren Sie es online!

Sundar - Setzen Sie Monica wieder ein
quelle
2

Gelee , 9 Bytes

ẸÐf÷g/$€E

Probieren Sie es online!

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

SageMath, 40 Bytes

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

Probieren Sie es online aus

Diese anonyme Funktion gibt zurück, Falsewenn die Matrix den ersten Rang hat, Trueandernfalls.

Die Funktion nimmt eine Matrix Mals Eingabe, konvertiert sie in eine reduzierte Zeilen-Staffel-Form ( M.rref()) und prüft, ob anydie Zeilen nach der ersten nicht Null sind. Dann wird dieser Wert mit multipliziert M.nrows()>1(hat die Matrix mehr als eine Zeile?).

Mego
quelle
1

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

Probieren Sie es online!

Wie es funktioniert

Prüft, ob eine 2-Moll-Zahl eine Determinante ungleich Null hat. Wenn dies der Fall ist, muss der Rang mindestens 2 sein: "Ein nicht verschwindendes p-Moll (p × p-Submatrix mit Nicht-Null-Determinante) zeigt, dass die Zeilen und Spalten dieser Submatrix linear unabhängig sind, und somit diese Zeilen und Spalten der Vollmatrix sind linear unabhängig (in der Vollmatrix), daher sind der Zeilen- und Spaltenrang mindestens so groß wie der Determinantenrang "(aus Wikipedia )

Hinweis: Dank des Kommentars von user71546 wurden zwei Bytes rasiert.

Luca Citi
quelle
1
91 - kürzer, wenn die Funktionsargumente mit Aufzählungen versehen werden und somit 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))
Folgendes überflüssig wird
@ user71546 Danke! Es gemacht!
Luca Citi