Submatri yang Benar-Benar Dapat Dibalik

16

(Terinspirasi oleh pertanyaan ini di atas tentang Matematika)

Definisi

Diberikan n x nmatriks kuadrat A , kita dapat menyebutnya invertiblejika ada beberapa n x nmatriks kuadrat B sedemikian sehingga AB = BA = I n , dengan I n menjadi matriks identitas ukuran n x n(matriks dengan diagonal utama 1s dan apa pun yang lain 0), dan AB dan BA yang mewakili perkalian matriks biasa (saya tidak akan membahasnya di sini - ambil kelas aljabar linier).

Dari itu, kami dapat memanggil m x nmatriks C totally invertible jika setiap k x ksubmatrix (didefinisikan di bawah) dari C dibalik untuk semua k > 1, k <= (smaller of m,n).

Sebuah submatrix didefinisikan sebagai matriks yang dihasilkan setelah penghapusan sejumlah baris dan / atau kolom dari matriks asli. Sebagai contoh, 3x3matriks C di bawah ini dapat ditransformasikan menjadi 2x2submatrix C ' dengan menghapus baris pertama 1 2 3dan kolom tengah 2 5 8sebagai berikut:

C = [[1 2 3]
     [4 5 6]    -->  C' = [[4 6]
     [7 8 9]]              [7 9]]

Perhatikan bahwa ada banyak kemungkinan submatrix yang berbeda, di atas hanyalah sebuah contoh. Tantangan ini hanya berkaitan dengan orang-orang di mana submatrix yang dihasilkan adalah k x k matriks persegi .

Tantangan

Diberikan matriks input, tentukan apakah itu benar-benar tidak dapat dibalik atau tidak.

Input

  • Satu matriks ukuran m x n, dalam format apa pun yang sesuai .
  • Tanpa kehilangan sifat umum, Anda dapat mengasumsikan m <= natau m >= n, yang mana golfier untuk kode Anda, dan mengambil input seperti itu (yaitu, Anda mendapatkan operasi transpos gratis jika Anda menginginkannya).
  • Ukuran matriks input tidak akan lebih kecil dari 3 x 3, dan tidak lebih besar dari bahasa Anda dapat menangani.
  • Matriks input hanya terdiri dari nilai numerik dari Z + ( bilangan bulat positif ).

Hasil

  • Nilai true / falsey untuk apakah matriks input benar-benar dapat dibalik.

Aturan

  • Program lengkap atau fungsi dapat diterima.
  • Celah standar dilarang.
  • Ini adalah sehingga semua aturan golf biasa berlaku, dan kode terpendek (dalam byte) menang.

Contohnya

Truthy

[[1 2 3]
 [2 3 1]
 [3 1 2]]

[[2 6 3]
 [1 12 2]
 [5 3 1]]

[[1 2 3 4]
 [2 3 4 1]
 [3 4 1 2]]

[[2  3  5  7  11]
 [13 17 19 23 29]
 [31 37 41 43 47]]


Falsey

[[1 2 3]
 [4 5 6]
 [7 8 9]]

[[1 6 2 55 3]
 [4 5 5 5  6]
 [9 3 7 10 4]
 [7 1 8 23 9]]

[[2 3 6]
 [1 2 12]
 [1 1 6]]

[[8 2 12 13 2]
 [12 7 13 12 13]
 [8 1 12 13 5]]
AdmBorkBork
sumber
Di mana submatrix singular berada 2 6 3; 1 12 2; 5 3 1?
feersum
1
@feersum Whoops - terima kasih atas tangkapannya. Seharusnya itu berada di bawah Truthy dan yang di bawahnya seharusnya berada 6di sudut, bukan a 7. Kesalahan ketik yang canggung.
AdmBorkBork
Pada awalnya, saya pikir judul mengatakan "kapal selam yang sama sekali tidak dapat dibalik".
user2357112 mendukung Monica

Jawaban:

5

Jelly , 26 24 23 20 19 17 16 byte

-1 byte terima kasih kepada @miles (tidak perlu untuk masing-masing ,, ketika mengambil determinan)
-2 byte, @miles lagi! (Pemisahan rantai yang tidak perlu, dan penggunaan Ѐcepat)

ZœcLÆḊ
œcЀJÇ€€Ȧ

TryItOnline! atau semua 8 tes

Bagaimana?

œcЀJÇ€€Ȧ  - Main link: matrix as an array, M
    J      - range of length -> [1,2,...,len(a)] (n)
  Ѐ       - for each of right argument
œc         -     combinations of M numbering n
     Ç€€   - call the last link (1) as a monad for €ach for €ach
        Ȧ  - all truthy (any determinant of zero results in 0, otherwise 1)
                 (this includes an implicit flattening of the list)

ZœcLÆḊ - Link 1, determinants of sub-matrices: row selection, s
Z      - transpose s
   L   - length of s
 œc    - combinations of transposed s numbering length of s
    ÆḊ - determinant
Jonathan Allan
sumber
Saya berpikir saya membutuhkannya karena saya memiliki banyak kombinasi, tetapi tidak, saya tidak perlu menginstruksikan secara eksplisit. Terima kasih!
Jonathan Allan
Saya belajar tentang hal itu dari tantangan terakhir menggunakan determinan, dan memverifikasi bahwa memang ada ldepth = 2di sumbernya
mil
1
Juga saya pikir Anda dapat menyimpan byte di link 2 menggunakan ZœcLÆḊdan byte lain di link utama olehçЀJȦ
mil
Good stuff @miles terima kasih lagi! Saya pikir yang pertama dari keduanya tidak bekerja ketika saya mencobanya, tapi itu pasti ketika saya menggunakan Anda bermain golf. Benar-benar lupa Ѐ.
Jonathan Allan
2
Kombinasi yang bagus, saya pikir Anda bisa membuatnya menjadi satu liner jika Anda mau dengan œcЀJµZœcLÆḊµ€€Ȧyang juga 16 byte
mil
4

Mathematica 10.0, 34 byte

#~Minors~n~Table~{n,Tr@#}~FreeQ~0&

Rantai 6-tilde ... catatan pribadi baru!

feersum
sumber
3

MATL, 57 byte

tZyt:Y@!"@w2)t:Y@!"@w:"3$t@:)w@:)w3$)0&|H*XHx]J)]xxtZy]H&

Tentu saja, Anda dapat mencobanya secara online!

Input harus dalam orientasi 'potret' (nRows> = nColumns). Saya merasa bahwa ini mungkin bukan solusi yang paling efisien ... Tapi setidaknya saya meninggalkan beberapa ruang bagi orang lain untuk mengalahkan saya. Saya akan senang mendengar petunjuk khusus yang bisa membuat pendekatan khusus ini lebih pendek, tetapi saya pikir ini bytecount besar harus menginspirasi orang lain untuk membuat entri MATL dengan pendekatan yang sama sekali berbeda. Menampilkan 0 jika salah, atau nilai besar jika benar (akan dengan cepat menjadi Inf jika matriks terlalu besar; untuk 1 byte tambahan, seseorang dapat mengganti H*dengan H&Y(logis dan)). Disimpan beberapa byte berkat @LuisMendo.

tZy  % Duplicate, get size. Note that n=<m.   
%   STACK:  [m n], [C]
t: % Range 1:m                           
%   STACK:  [1...m], [m n], [C]
Y@   % Get all permutations of that range. 
%   STACK:  [K],[m n],[C] with K all perms in m direction.
!"   % Do a for loop over each permutation.
%   STACK:  [m n],[C], current permutation in @.
@b   % Push current permutation. Bubble size to top.
%   STACK:  [m n],[pM],[C] with p current permutation in m direction.
2)t:Y@!" % Loop over all permutations again, now in n direction
%   STACK: [n],[pM],[C] with current permutation in @.
@w:" % Push current permutation. Loop over 1:n (to get size @ x @ matrices)
%   STACK: [pN],[pM],[C] with loop index in @.
3$t  % Duplicate the entire stack.
%   STACK: [pN],[pM],[C],[pN],[pM],[C]
@:)  % Get first @ items from pN
%   STACK: [pNsub],[pM],[C],[pN],[pM],[C]
w@:) % Get first @ items from pM
%   STACK: [pMsub],[pNsub],[C],[pN],[pM],[C]
w3$)  % Get submatrix. Needs a `w` to ensure correct order.
%   STACK: [Csub],[pN],[pM],[C]
0&|  % Determinant.
%   STACK: [det],[pN],[pM],[C]
H*XHx% Multiply with clipboard H.
%   STACK: [pN],[pM],[C]
]    % Quit size loop
%   STACK: [pN],[pM],[C]. Expected: [n],[pM],[C]
J)   % Get last element from pN, which is n.
%   STACK: [n],[pM],[C]
]    % Quit first loop
xxtZy% Reset stack to
%   STACK: [m n],[C]
]    % Quit final loop.
H& % Output H only.
Sanchises
sumber