Membangun vektor pada posisi umum

Biarkan matriks nyata ( ) dengan properti yang ada dalam koleksi kolom adalah peringkat penuh. $k\times n$ $k\le n$ ${\bf A}$ $k$

T: Apakah ada cara yang efisien untuk secara deterministik menemukan vektor sehingga matriks yang diperbesar mempertahankan properti yang sama dengan : setiap kolom adalah peringkat penuh. ${\bf a}$ ${\bf A}' = [{\bf A}\;{\bf a}]$ ${\bf A}$ $k$

Sidenote yang Relevan: Matriks yang memiliki properti ini adalah generator dari Kode Reed-Solomon: menambahkan kolom yang mempertahankan struktur Vandermonde mempertahankan properti peringkat. $(n,k)$

ds.algorithms linear-algebra matrices coding-theory Dimitris
sumber

Saya tidak yakin apakah saya mengerti maksud Anda. Saya membutuhkan , tidak menjadi masalah.

k \leq n

$k\le n$

k = n

$k=n$

Dimitris

@ Jɛ ﬀ Ek tidak berubah: dalam kasus k = n, hanya n dari kolom (sekarang) n + 1 yang perlu peringkat penuh. Dalam hal ini, masalahnya haruslah mudah: temukan transformasi affine dari matriks ke basis ortogonal dari R ^ n, dan kemudian biarkan a menjadi vektor yang gambarnya di bawah ini adalah semua vektor 1s.

Suresh Venkat

Tampak bagi saya bahwa ini harus menjadi cara untuk melakukan ini melalui Grassmanian, tapi saya tidak mengerti caranya.

Suresh Venkat

@ Suresh Ya memang, untuk kasus n = k + 1 sepertinya bisa dipecahkan dengan cara yang Anda sebutkan. Atau Anda cukup memilih untuk berada di ruang nol dari semua , -koleksi vektor.

a

${\bf a}$

k

$k$

(k - 1)

$(k-1)$

Dimitris

pertanyaan yang bagus Kedengarannya seperti versi yang lebih lemah dari masalah memverifikasi properti isometry terbatas, yang terbuka lebar sejauh yang saya tahu.

Sasho Nikolov

Jawaban:

Jika Anda memilih seragam secara acak dari hypercube , matriks akan memiliki properti yang diinginkan dengan probabilitas . $\mathbf{a}$ $[0,1]^n$ $[\mathbf{A}~ \mathbf{a}]$ $1$

Jeffε
sumber

Saya tidak bisa tidak setuju :). Masalahnya muncul ketika Anda ingin memeriksa bahwa vektor seperti itu berfungsi (tidak masalah jika itu berfungsi). Anda harus memeriksa subset kolom. Masalah pengecekan ini menjadi lebih relevan ketika Anda mempertimbangkan bidang terbatas (dari pesanan tetap), tetapi saya mencoba untuk menghindari membicarakannya.

(\binom{n}{k})

${{n}\choose{k}}$

Dimitris

Pertanyaannya secara spesifik menanyakan algoritma deterministik yang efisien . Jika Anda menjawab sesuatu yang terkait tetapi tidak memenuhi kondisi yang disebutkan dalam pertanyaan, Anda harus mengatakannya secara eksplisit menurut pendapat saya.

Tsuyoshi Ito

@ TsuyoshiIto apa, Anda tidak suka anak kucing? :)

Suresh Venkat

@ Suresh: Dalam praktiknya, akan menyenangkan jika komputer saya tiba-tiba berubah menjadi anak kucing. Secara teori, pertama-tama Anda harus mendefinisikan anak kucing.

Tsuyoshi Ito

@ Jɛ ﬀ E Mungkin saya harus menjelaskan mengapa pertanyaan ini menarik. Pertanyaan sebenarnya adalah sama tetapi lebih dari bidang terbatas, tetapi saya cenderung berpikir bahwa bidang mempersulit pertanyaan aljabar linier. Aplikasi ini adalah desain dari matriks generator kode "baik". Yang acak (entri id) dapat ditampilkan untuk memuaskan properti whp, menggunakan alat seperti lemma Schwartz-Zippel. Untuk masalah ini SZ biasanya membutuhkan perintah lapangan dan Anda tidak dapat secara efisien memeriksa bahwa matriks benar-benar berfungsi. Mengapa ini penting? Karena kode yang paling mungkin andal terkadang tidak disukai.

O (2^{k})

$O(2^k)$

Dimitris