Czy macierz jest na pierwszym miejscu?

21

Biorąc pod uwagę macierz liczb całkowitych, sprawdź, czy jest na pierwszym miejscu, co oznacza, że ​​każdy wiersz jest wielokrotnością tego samego wektora. Na przykład w

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

każdy rząd jest wielokrotnością 1 0 -10 5.

Ta sama definicja działa również z kolumnami zamiast wierszy. Alternatywnie macierz jest na pierwszym miejscu, jeśli jest jak tabliczka mnożenia:

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

Przypisaliśmy etykiety wierszy r[i]i kolumny, c[j]aby każdy wpis macierzy M[i][j]był iloczynem odpowiednich etykiet as M[i][j] = r[i] * c[j].

Wkład:

Macierz liczb całkowitych jako wybrany kontener 2D. Na przykład lista list, tablica 2D lub podobne. Nie należy traktować szerokości ani wysokości jako dodatkowych danych wejściowych, chyba że wymaga tego format tablicy.

Matryca może być niekwadratowa. Będzie miał co najmniej jeden niezerowy wpis - nie musisz zajmować się pustymi lub zerowymi matrycami.

Możesz założyć, że liczby całkowite nie spowodują problemów z przepełnieniem.

Wydajność:

Spójna wartość dla macierzy pierwszego rzędu i inna spójna wartość dla innych macierzy.

Wbudowane:

Nie możesz używać żadnego wbudowanego do obliczania rangi ani bezpośrednio sprawdzać rangi 1. Możesz użyć innych wbudowanych wartości, takich jak wartości własne, dekompozycje itp., Ale zachęcam do głosowania na odpowiedzi, które nie mają wbudowanych, wykonują większość pracy.

Przypadki testowe:

1. miejsce:

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

Nie na pierwszym miejscu:

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

Tabela liderów:

xnor
źródło
2
Dla ciekawskich odpowiedź Mathematica z wykorzystaniem wbudowanych wyglądałaby tak (16 bajtów):MatrixRank@#==1&
JungHwan Min
Powiązane
mile
2
Piękne twierdzenie jest takie, że ranga kolumny jest równa rangi rzędu dla macierzy o skończonych wymiarach.
Leaky Nun
3
Czy musimy martwić się problemami z precyzją pływaka? Mogą sprawić, że matryca rangi 1 wydaje się na przykład rangą 2
Luis Mendo
@LuisMendo Musisz poradzić sobie z problemami z precyzją, takimi jak wartości własne 1.0000000001, ale możesz założyć, że matryca nie jest duża i nie została specjalnie wybrana do błędnej klasyfikacji.
xnor

Odpowiedzi:

13

Galaretka , 6 bajtów

ẸÐfÆrE

Wypróbuj online!

Jak to działa

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

Precyzja

Ærużywa metod numerycznych, więc jego wyniki są zwykle niedokładne. Na przykład dane wejściowe [6, -5, 1] , które reprezentują wielomian 6–5x + x² , dają pierwiastki 3,0000000000000004 i 1,9999999999999998 . Jednak pomnożenie wszystkich współczynników wielomianu przez tę samą niezerową stałą powoduje równie niedokładne pierwiastki. Na przykład Æruzyskuje te same pierwiastki dla [6, -5, 1] i [6 × 10 100 , -5 × 10 100 , 10 100 ] .

Należy zauważyć, że ograniczona precyzja pływaka i typów złożonych może prowadzić do błędów. Na przykład Æruzyskałby te same pierwiastki dla [1, 1] i [10 100 , 10 100 + 1] . Ponieważ możemy założyć, że matryca nie jest duża i nie została specjalnie wybrana do błędnej klasyfikacji , to powinno być w porządku.

Dennis
źródło
5
pomnożenie wszystkich współczynników wielomianu przez tę samą niezerową stałą daje równie niedokładne pierwiastki. To genialne podejście
Luis Mendo,
8

Haskell , 50 bajtów

rpobiera listę list Integers i zwraca, Falsejeśli macierz ma rangę 1, w Trueprzeciwnym razie.

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

Wypróbuj online!

Jak to działa

  • Generuje wszystkie pary wierszy ai b(w tym równe rzędy), a dla każdej pary pozwala xi yprzebiega przez odpowiednie elementy.
  • Mnoży rząd bprzez xi rząd aprzez y. Macierz będzie miała rangę 1 wtedy i tylko wtedy, gdy wyniki będą zawsze równe.
  • Ponieważ pary są generowane w obu zamówieniach, <można ich użyć do sprawdzenia, czy kiedykolwiek występuje nierówność. Lista wyników testu jest łączona z orpodaniem, Truejeśli istnieją wiersze nieproporcjonalne.
Ørjan Johansen
źródło
7

Mathematica, 51 33 bajtów

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

Wkład

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

-14 bajtów od user202729 Jeszcze
3 bajty zapisane od junghwanmin

J42161217
źródło
Sugeruję, że zamiast konstruować tabelę o długości równej tej First@#, można obliczyć, 0First@#ponieważ 0 mnoży ze wszystkim wynosi 0, a mnożenie można wyliczyć. Możesz także rozważyć użycie Tr[1^<list>]do obliczenia długości listy.
user202729,
bardzo fajnie. Będę edytować!
J42161217,
Zamiast 0#&@@#, {0..}będzie działać zbyt. A potem Infixdziała, więc końcowy kod może być RowReduce@#~Count~{0..}==Tr[1^#]-1&, oszczędzając 2 bajty.
JungHwan Min
W rzeczywistości Exceptmożna go użyć do pozbycia się Trrzeczy. -3 bajty:RowReduce@#~Count~Except@{0..}==1&
JungHwan Min
Myślę, że macierz o zmniejszonej liczbie wierszy jest gwarantowana jako niezerowa (ponieważ pierwotna macierz jest niezerowa), dlatego wynik zliczania będzie dodatnią liczbą całkowitą, dlatego <2można jej użyć zamiast ==1.
user202729,
4

JavaScript (ES6), 68 67 65 bajtów

Ten oparty jest na odpowiedzi Neila 05AB1E i jest znacznie bardziej wydajny niż moje oryginalne podejście.

Zwraca falseza miejsce pierwsze i trueinne.

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

Przypadki testowe


Oryginalna odpowiedź, 84 bajtów

Zwraca falseza miejsce pierwsze i trueinne.

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

Przypadki testowe

W jaki sposób?

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

Odejmowanie przeprowadzane na końcu kodu może prowadzić do wielu różnych sytuacji, które zostały podsumowane poniżej:

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

Test nie tak szybko, jak to uzyskać wartość truthy: to się dzieje, gdy mamy do czynienia z dwóch różnych wskaźników (inne niż 0/0 ) między a (i, y) i a (i, R) w każdym rzędzie Y matrycy, gdzie r jest indeksem niezerowego wiersza.

Arnauld
źródło
Huh, po prostu zastanawiałem się nad tym ...
Neil
@Neil Czy chcesz opublikować to jako nową odpowiedź? Po prostu daj mi znać.
Arnauld,
3

Python 2 + numpy, 58 bajtów

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

Wypróbuj online!

Uznanie za to .

całkowicie ludzki
źródło
Czy można użyć 1e-9zamiast 1e-10?
Jonathan Frech,
3

Galaretka , 12 bajtów

ẸÐfµ÷"ЀZE€Ẹ

Wypróbuj online!

Wyjaśnienie

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

Wyjaśnienie może być nieco niepoprawne, ponieważ jest to moja interpretacja golfa mil mojego oryginalnego algorytmu

-5 bajtów dzięki milom

HyperNeutrino
źródło
... Twój kod jest uzależniony od pieniędzy. (Dostaję deja vu ...)
całkowicieludzki
@icrieverytim Hej, tym razem przynajmniej liczba znaków dolara jest mniejsza niż połowa długości kodu! : P
HyperNeutrino,
1
@icrieverytim naprawił błąd, a teraz jeszcze mniej znaków dolara: P
HyperNeutrino
Uważam, że powinno to również działać dla 12 bajtów ẸÐfµ÷"ЀZE€Ẹ TIO
mil
@miles Oh nice! Twoje podejście jest nieco inne (tak myślę?), Więc możesz to opublikować jako własną odpowiedź, którą chcesz :)
HyperNeutrino
3

05AB1E , 16 bajtów

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

Wypróbuj online! Wykorzystuje właściwość tablicy mnożenia, że ​​przeciwległe rogi dowolnego prostokąta mają ten sam produkt. Wyjaśnienie:

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
źródło
3

TI-Basic (seria TI-83), 28 27 28 bajtów (62 znaki)

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

Oblicza formę macierzy [A]i szeregu, zapisuje pierwszy wiersz (do odrzucenia) L₁i drugi wiersz w ᶫX. Wtedy max(abs(ᶫXbędzie zero, jeśli ᶫXskłada się tylko z zer, a w przeciwnym razie wartość dodatnia, która not(zmienia się na 1, jeśli macierz ma rangę 1, w przeciwnym razie 0.

W przypadku macierzy 1-wierszowej ᶫXjest ustawiona na, {0}a następnie nie ulega zmianie, gdy próbujemy spojrzeć na nieistniejący drugi wiersz matrycy.


-1 bajt dzięki Scott Milner

+1 bajt, aby naprawić błąd wymiaru dla macierzy 1-rzędowych. Okazuje się, że Matr►list( polecenie narzeka, jeśli spróbujesz wyodrębnić drugi wiersz z macierzy za pomocą tylko jednego wiersza; jeśli jednak spróbujesz wyodrębnić pierwszy i drugi wiersz z macierzy, nastąpi to po cichu.

Misza Ławrow
źródło
1
Możesz zapisać bajt za pomocą Prompt [A]zamiast Ans→[A].
Scott Milner,
@ScottMilner Thanks! Prawdopodobnie istnieje sposób, aby tego uniknąć, jeśli użyjemy czegoś takiego jak ClrListinicjalizacja ᶫX, ale nie do końca dostałem to do pracy na mniejszej przestrzeni.
Misha Lavrov,
Pozbądź się drugiej linii, ponieważ Matr►list(zastąpi listę, nawet jeśli ona nie istnieje, a zaoszczędzisz 5 bajtów.
kamoroso94,
1
@ kamoroso94 Celem drugiego wiersza nie jest tworzenie listy, gdy nie istnieje: celem drugiego wiersza jest utworzenie wartości domyślnej dla drugiego wiersza, gdy macierz ma tylko jeden wiersz. Jeśli pozbędziesz się drugiej linii, kod ulega awarii dla macierzy 1xN.
Misha Lavrov,
2
@ kamoroso94 Musielibyśmy zastąpić L1 ᶫY, a nie Y; w przeciwnym razie kalkulator pomyśli „wyodrębnij Y-ty rząd macierzy do ᶫX”, a nie „wyodrębnij pierwszy rząd do ᶫY, a drugi rząd do ᶫX”.
Misza Ławrow
3

Brachylog , 27 bajtów

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

Wypróbuj online!

Wykorzystuje podejście Neila, że ​​„iloczyn przeciwległych narożników każdego prostokąta powinien być równy”. Produkt krzyżowy jest kosztowny i zajmuje 10 pełnych bajtów, ale wciąż jest krótszy niż jakakolwiek metoda oparta na podziale, którą wypróbowałem, głównie z powodu ustalenia dwóch spójnych wyników dla prawdy i falseya w pytaniu - czyniąc falsey tylko false., a nie czasem błąd dzielenia przez zero, zużywa zbyt wiele bajtów.

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

Alternatywne podejście oparte na podziale na elementy ( 30 bajtów ):

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

Wypróbuj online!

sundar - Przywróć Monikę
źródło
2

Galaretka , 9 bajtów

ẸÐf÷g/$€E

Wypróbuj online!

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

SageMath, 40 bajtów

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

Wypróbuj online

Ta anonimowa funkcja zwraca, Falsejeśli macierz jest na pierwszym miejscu, i w Trueprzeciwnym razie.

Ta funkcja pobiera macierz Mjako dane wejściowe, konwertuje ją na zredukowaną formę ( M.rref()) wiersza-echelon i sprawdza, anyczy wiersze za pierwszym nie są zerowe. Następnie wartość ta jest mnożona przez M.nrows()>1(czy macierz ma więcej niż jeden wiersz?).

Mego
źródło
1

Python 3 , 93 91 bajtów

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

Wypróbuj online!

Jak to działa

Sprawdza, czy jakikolwiek 2-moll ma niezerową determinantę. Jeśli tak jest, ranga musi wynosić co najmniej 2: „Nie znikająca p-moll (submatrix p × p z determinantą niezerową) pokazuje, że wiersze i kolumny tej submatrix są liniowo niezależne, a zatem te wiersze i kolumny pełnej macierzy są liniowo niezależne (w pełnej macierzy), więc ranga wiersza i kolumny jest co najmniej tak duża jak ranga determinantyczna "(od Wikipedii )

Uwaga: ogolono dwa bajty dzięki komentarzowi użytkownika user71546.

Luca Citi
źródło
1
91 - krótszy, jeśli wstawiamy wyliczenia do argumentów funkcji, a tym samym eliminujemy potrzebę 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 Dzięki! Zrobione!
Luca Citi,