21

Dada una matriz de enteros, pruebe si es de rango uno, lo que significa que cada fila es un múltiplo del mismo vector. Por ejemplo, en

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

cada fila es un múltiplo de 1 0 -10 5.

La misma definición también funciona con columnas en lugar de filas. Alternativamente, una matriz es de rango uno si es como una tabla de multiplicar:

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

Hemos asignado etiquetas de fila r[i]y etiquetas de columna c[j]para que cada entrada de matriz M[i][j]sea el producto de las etiquetas correspondientes como M[i][j] = r[i] * c[j].

Entrada:

Una matriz entera como contenedor 2D de su elección. Por ejemplo, una lista de listas, una matriz 2D o similar. No debe tomar el ancho o la altura como entradas adicionales a menos que el formato de matriz lo requiera.

La matriz puede ser no cuadrada. Tendrá al menos una entrada distinta de cero: no tiene que lidiar con matrices vacías o cero.

Puede suponer que los enteros no causarán problemas de desbordamiento.

Salida:

Un valor consistente para matrices de rango uno, y un valor consistente diferente para otras matrices.

Incorporados:

No puede utilizar ninguna función integrada para calcular el rango o verificar directamente el rango uno. Puede usar otros elementos integrados, como valores propios, descomposiciones, etc., pero le recomiendo que vote por respuestas que no tienen elementos integrados que hacen la mayor parte del trabajo.

Casos de prueba:

Rango uno:

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

No rango uno:

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

Tabla de clasificación:

Mostrar fragmento de código

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>

Expandir fragmento

code-golf decision-problem matrix linear-algebra xnor
fuente

2

Para los curiosos, una respuesta de Mathematica usando builtins se vería así (16 bytes):MatrixRank@#==1&

JungHwan Min

Relacionado

millas

2

Un hermoso teorema es que el rango de columna es igual al rango de fila para matrices de dimensiones finitas.

Leaky Nun

3

¿Tenemos que preocuparnos por problemas de precisión de flotación? Pueden hacer que una matriz de rango 1 parezca rango 2, por ejemplo

Luis Mendo

@LuisMendo Debe manejar problemas de precisión como valores propios de 1.0000000001, pero puede suponer que la matriz no es grande y no está específicamente elegida para ser mal clasificada.

xnor

13

Jalea , 6 bytes

ẸÐfÆrE

Pruébalo en línea!

Cómo funciona

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

Precisión

Ærutiliza métodos numéricos, por lo que sus resultados suelen ser inexactos. Por ejemplo, la entrada [6, -5, 1] , que representa el polinomio 6 - 5x + x² , da como resultado las raíces 3.0000000000000004 y 1.9999999999999998 . Sin embargo, multiplicar todos los coeficientes de un polinomio por la misma constante que no sea cero da como resultado raíces igualmente inexactas. Por ejemplo, Ærobtiene las mismas raíces para [6, -5, 1] y [6 × 10 ¹⁰⁰ , -5 × 10 ¹⁰⁰ , 10 ¹⁰⁰ ] .

Cabe señalar que la precisión limitada del flotador y los tipos complejos pueden conducir a errores. Por ejemplo, Ærobtendría las mismas raíces para [1, 1] y [10 ¹⁰⁰ , 10 ¹⁰⁰ + 1] . Como podemos suponer que la matriz no es grande y no está elegida específicamente para ser mal clasificada , eso debería estar bien.

Dennis
fuente

55

multiplicando todos los coeficientes de un polinomio por los mismos que no son cero constantes resultados en las raíces igualmente inexactas eso es un enfoque brillante

Luis Mendo

8

Haskell , 50 bytes

rtoma una lista de listas de Integersy devuelve Falsesi la matriz tiene rango uno, de lo Truecontrario.

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

Pruébalo en línea!

Cómo funciona

Genera todos los pares de filas ay b(incluidas las filas iguales), y para cada par, permite xy yejecuta los elementos correspondientes.
Multiplica la fila bpor xy la fila apor y. La matriz tendrá rango uno si y solo si los resultados son siempre iguales.
Dado que los pares se generan en ambos órdenes, <se pueden usar para verificar si alguna vez hay una desigualdad. La lista de resultados de la prueba se combina con or, dando Truesi hay filas no proporcionales.

Ørjan Johansen
fuente

7

Mathematica, 51 33 bytes

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

Entrada

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

-14 bytes del usuario202729
3 bytes más guardados de junghwanmin

J42161217
fuente

Sugiero que, en lugar de construir una tabla con una longitud igual a la de First@#, puede calcular, 0First@#ya que 0 se multiplica con todo es 0, y la multiplicación es listable. También puede considerar usar Tr[1^<list>]para calcular la longitud de una lista.

user202729

muy bonito ¡editaré!

J42161217

En lugar de 0#&@@#, {0..}funcionaría también. Y luego Infixfunciona, por lo que el código final podría ser RowReduce@#~Count~{0..}==Tr[1^#]-1&, ahorrando 2 bytes.

JungHwan Min

En realidad, Exceptse puede usar para deshacerse de las Trcosas. -3 bytes:RowReduce@#~Count~Except@{0..}==1&

JungHwan Min

Creo que se garantiza que la matriz de filas reducidas sea distinta de cero (porque la matriz original es distinta de cero), por lo tanto, el resultado del recuento será un entero positivo, por lo que <2se puede utilizar en lugar de ==1.

user202729

4

JavaScript (ES6), 68 67 65 bytes

Este se basa en la respuesta 05AB1E de Neil y es significativamente más eficiente que mi enfoque original.

Devoluciones falsepara rango uno y de trueotra manera.

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

Casos de prueba

Mostrar fragmento de código

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

Expandir fragmento

Respuesta original, 84 bytes

Devoluciones falsepara rango uno y de trueotra manera.

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

Casos de prueba

Mostrar fragmento de código

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

Expandir fragmento

¿Cómo?

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 resta que se realiza al final del código puede conducir a muchas situaciones diferentes, que se resumen a continuación:

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

La prueba falla tan pronto como obtenemos un valor Truthy: esto ocurre cuando nos encontramos con dos proporciones diferentes (distintos de 0/0 ) entre un (i, y) y a (i, r) en cualquier fila y de la matriz, donde r es el índice de una fila distinta de cero.

Arnauld
fuente

Huh, me preguntaba que yo mismo ...

Neil

@Neil ¿Desea publicarlo como una nueva respuesta? Sólo házmelo saber.

Arnauld

3

Python 2 + numpy, 58 bytes

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

Pruébalo en línea!

Crédito a esto .

totalmente humano
fuente

¿Se podría usar en 1e-9lugar de 1e-10?

Jonathan Frech

3

Jalea , 12 bytes

ẸÐfµ÷"Ð€ZE€Ẹ

Pruébalo en línea!

Explicación

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

La explicación puede ser ligeramente incorrecta ya que esta es mi interpretación del golf de millas de mi algoritmo original

-5 bytes gracias a millas

Hiperneutrino
fuente

... Tu código es adicto al dinero. (Me estoy poniendo deja vu ...)

totalmente humano

@icrieverytim ¡Hola, al menos el número de signos de dólar es menos de la mitad de la longitud del código esta vez! : P

HyperNeutrino

1

@icrieverytim corrigió un error y ahora aún menos signos de dólar: P

HyperNeutrino

Creo que esto también debería funcionar para ẸÐfµ÷"Ð€ZE€Ẹ TIO

millas del

@miles ¡Qué bien! El enfoque para el tuyo es un poco diferente (¿creo?), Así que puedes publicarlo como tu propia respuesta que quieras :)

HyperNeutrino

3

05AB1E , 16 bytes

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

Pruébalo en línea! Utiliza la propiedad de la tabla de multiplicar de que las esquinas opuestas de cualquier rectángulo tienen el mismo producto. Explicación:

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
fuente

3

TI-Basic (serie TI-83), 28 27 28 bytes (62 caracteres)

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

Calcula la forma fila-escalón de la matriz [A], almacena su primera fila (para descartar) L₁y su segunda fila ᶫX. Entonces max(abs(ᶫXserá cero si ᶫXconsta solo de ceros, y un valor positivo de lo contrario, que not(cambia a 1 si la matriz es de rango uno, 0 de lo contrario.

Para una matriz de 1 fila, ᶫXse establece en {0}y luego no cambia cuando intentamos mirar la segunda fila inexistente de la matriz.

-1 byte gracias a Scott Milner

+1 byte para corregir el error de dimensión para matrices de 1 fila. Resulta que el Matr►list( comando se queja si intenta extraer la segunda fila de una matriz con solo una fila; sin embargo, si intenta extraer la primera y la segunda fila de la matriz, fallará en silencio.

Misha Lavrov
fuente

1

Puede guardar un byte con en Prompt [A]lugar de Ans→[A].

Scott Milner

@ScottMilner ¡Gracias! Probablemente haya una forma de evitarlo si usamos algo como ClrListinicializar ᶫX, pero no he logrado que funcione en menos espacio.

Misha Lavrov

Deshágase de la segunda línea, ya Matr►list(que sobrescribirá la lista, incluso si no existe, y ahorrará 5 bytes.

kamoroso94

1

@ kamoroso94 El punto de la segunda línea no es crear una lista cuando no existe: el punto de la segunda línea es crear un valor predeterminado para la segunda fila cuando la matriz solo tiene una fila. Si se deshace de la segunda línea, el código se bloquea para matrices 1xN.

Misha Lavrov

2

@ kamoroso94 Tendríamos que reemplazar L1 con ᶫY, no Y; de lo contrario, la calculadora pensará "extraer la fila Y de la matriz a ᶫX", no "extraer la primera fila a ᶫY y la segunda fila a ᶫX".

Misha Lavrov

3

Brachylog , 27 bytes

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

Pruébalo en línea!

Utiliza el enfoque de Neil de "los productos de las esquinas opuestas de cada rectángulo deben ser iguales". El producto cruzado es costoso y toma 10 bytes completos, pero esto es aún más corto que cualquier enfoque basado en la división que probé, principalmente debido a la estipulación de dos resultados consistentes para la verdad y falsey en la pregunta, lo que hace que falsey sea solo un false., y no a veces un error de división por cero, utiliza demasiados 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.)

Enfoque alternativo basado en la división por elementos ( 30 bytes ):

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

Pruébalo en línea!

sundar - Restablecer a Monica
fuente

2

Jalea , 9 bytes

ẸÐf÷g/$€E

Pruébalo en línea!

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

Lynn
fuente

1

SageMath, 40 bytes

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

Pruébalo en línea

Esta función anónima regresa Falsesi la matriz es de rango uno, y de lo Truecontrario.

La función toma una matriz Mcomo entrada, la convierte en una forma reducida de fila-escalón ( M.rref()) y comprueba si anylas filas más allá de la primera no son cero. Entonces, ese valor se multiplica por M.nrows()>1(¿la matriz tiene más de una fila?).

Mego
fuente

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

Pruébalo en línea!

Cómo funciona

Comprueba si algún 2-menor tiene un determinante distinto de cero. Si este es el caso, el rango debe ser al menos 2: "Una p-menor que no desaparece (submatriz p × p con determinante distinto de cero) muestra que las filas y columnas de esa submatriz son linealmente independientes y, por lo tanto, esas filas y las columnas de la matriz completa son linealmente independientes (en la matriz completa), por lo que el rango de fila y columna es al menos tan grande como el rango determinante "(de Wikipedia )

Nota: afeitó dos bytes gracias al comentario de user71546.

Luca Citi
fuente

1

91 - más corto si pone enumerar en los argumentos de la función y así elimina la necesidad 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 ¡Gracias! ¡Hecho!

Luca Citi

0

Pari / GP , 18 bytes

a->#matimage(a)==1

matimage da una base de la imagen de la transformación lineal definida por la matriz.

Pruébalo en línea!

alephalpha
fuente

¿Es la matriz de rango uno?

Respuestas:

Jalea , 6 bytes

Cómo funciona

Precisión

Haskell , 50 bytes

Cómo funciona

Mathematica, 51 33 bytes

JavaScript (ES6), 68 67 65 bytes

Casos de prueba

Respuesta original, 84 bytes

Casos de prueba

¿Cómo?

Python 2 + numpy, 58 bytes

Jalea , 12 bytes

Explicación

05AB1E , 16 bytes

TI-Basic (serie TI-83), 28 27 28 bytes (62 caracteres)

Brachylog , 27 bytes

Jalea , 9 bytes

SageMath, 40 bytes

Python 3 , 93 91 bytes

Pari / GP , 18 bytes