У лінійній алгебрі, циркулянт — особливий підвид матриць Тепліца, в якій кожен вектор-стовпчик являє собою попередній вектор стовпчик циклічно зсунутий на один елемент праворуч. У обчислювальній математиці, циклічні матриці важливі, бо воно діагоналізовні за допомогою дискретного перетворення Фур'є, тобто, лінійні рівняння, які містять їх можна розв'язати застосувавши швидке перетворення Фур'є. Їх можна інтерпретувати аналітично як інтегральне ядро згортки циклічної групи тому вони часто з'являються у формальних описах просторово інваріантних лінійних операцій. У криптографії, циклічні матриці використовуються в MixColumns етапі в Advanced Encryption Standard.
Означення
циркулянт
має вигляд
Один вектор що з'являється в першому стовпці
повністю визначає циркулянт. Інші стовпці
є циклічними переставками вектора
зі зсувом, що дорівнює індексу стовпця. Останній рядок
є вектором
у зворотньому порядку, а інші рядки є його циклічними переставками.
Многочлен називається пов'язаним многочленом матриці
Властивості
Власні вектори і значення
Нормалізовані власні вектори циркулянта задаються як
де є n-м коренем з одиниці, а
це уявна одиниця.
Відповідні власні значення такі
Визначник
Визначник циркулянта можна обчислити як:
Оскільки транспонування не змінює власні значення матриці, то тотожним формулюванням є
Помножимо циркулянт праворуч на визначник Вандермонда типу :
Тепер скорочуємо на визначник Вандермонда як ненульовий.■
Ранг
Див. також
Примітки
- Philip J. Davis, Circulant Matrices, Wiley, New York, 1970
- A. W. Ingleton (1956). The Rank of Circulant Matrices. J. London Math. Soc. s1-31 (4): 445—460. doi:10.1112/jlms/s1-31.4.445.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U linijnij algebri cirkulyant osoblivij pidvid matric Teplica v yakij kozhen vektor stovpchik yavlyaye soboyu poperednij vektor stovpchik ciklichno zsunutij na odin element pravoruch U obchislyuvalnij matematici ciklichni matrici vazhlivi bo vono diagonalizovni za dopomogoyu diskretnogo peretvorennya Fur ye tobto linijni rivnyannya yaki mistyat yih mozhna rozv yazati zastosuvavshi shvidke peretvorennya Fur ye Yih mozhna interpretuvati analitichno yak integralne yadro zgortki ciklichnoyi grupi Z n Z displaystyle mathbb Z n mathbb Z tomu voni chasto z yavlyayutsya u formalnih opisah prostorovo invariantnih linijnih operacij U kriptografiyi ciklichni matrici vikoristovuyutsya v MixColumns etapi v Advanced Encryption Standard Oznachennyan n displaystyle n times n cirkulyant C displaystyle C maye viglyad C c 0 c n 1 c 2 c 1 c 1 c 0 c n 1 c 2 c 1 c 0 c n 2 c n 1 c n 1 c n 2 c 1 c 0 displaystyle C begin bmatrix c 0 amp c n 1 amp dots amp c 2 amp c 1 c 1 amp c 0 amp c n 1 amp amp c 2 vdots amp c 1 amp c 0 amp ddots amp vdots c n 2 amp amp ddots amp ddots amp c n 1 c n 1 amp c n 2 amp dots amp c 1 amp c 0 end bmatrix Odin vektor c displaystyle c sho z yavlyayetsya v pershomu stovpci C displaystyle C povnistyu viznachaye cirkulyant Inshi stovpci C displaystyle C ye ciklichnimi perestavkami vektora c displaystyle c zi zsuvom sho dorivnyuye indeksu stovpcya Ostannij ryadok C displaystyle C ye vektorom c displaystyle c u zvorotnomu poryadku a inshi ryadki ye jogo ciklichnimi perestavkami Mnogochlen f x c 0 c 1 x c n 1 x n 1 displaystyle f x c 0 c 1 x dots c n 1 x n 1 nazivayetsya pov yazanim mnogochlenom matrici C displaystyle C VlastivostiVlasni vektori i znachennya Normalizovani vlasni vektori cirkulyanta zadayutsya yak v j 1 n 1 w j w j 2 w j n 1 T j 0 1 n 1 displaystyle v j frac 1 sqrt n 1 omega j omega j 2 ldots omega j n 1 T quad j 0 1 ldots n 1 de w j exp 2 p i j n displaystyle omega j exp left tfrac 2 pi ij n right ye n m korenem z odinici a i displaystyle i ce uyavna odinicya Vidpovidni vlasni znachennya taki l j c 0 c n 1 w j c n 2 w j 2 c 1 w j n 1 j 0 n 1 displaystyle lambda j c 0 c n 1 omega j c n 2 omega j 2 ldots c 1 omega j n 1 qquad j 0 ldots n 1 Viznachnik Viznachnik cirkulyanta mozhna obchisliti yak d e t C j 0 n 1 c 0 c n 1 w j c n 2 w j 2 c 1 w j n 1 displaystyle mathrm det C prod j 0 n 1 c 0 c n 1 omega j c n 2 omega j 2 dots c 1 omega j n 1 Oskilki transponuvannya ne zminyuye vlasni znachennya matrici to totozhnim formulyuvannyam ye d e t C j 0 n 1 c 0 c 1 w j c 2 w j 2 c n 1 w j n 1 j 0 n 1 f w j displaystyle mathrm det C prod j 0 n 1 c 0 c 1 omega j c 2 omega j 2 dots c n 1 omega j n 1 prod j 0 n 1 f omega j Dovedennya Pomnozhimo cirkulyant pravoruch na viznachnik Vandermonda tipu w j i 1 n n displaystyle omega j i 1 n times n a 1 a 2 a n a n a 1 a n 1 a 2 a 3 a 1 1 1 1 w 1 w 2 w n w 1 n 1 w 2 n 1 w n n f w 1 f w 2 f w n w 1 f w 1 w 2 f w 2 w n f z n w 1 n 1 f w 1 w 2 n 1 f w 2 w n n 1 f w n displaystyle begin vmatrix a 1 amp a 2 amp cdots amp a n a n amp a 1 amp cdots amp a n 1 vdots amp vdots amp ddots amp vdots a 2 amp a 3 amp cdots amp a 1 end vmatrix cdot begin vmatrix 1 amp 1 amp cdots amp 1 omega 1 amp omega 2 amp cdots amp omega n vdots amp vdots amp ddots amp vdots omega 1 n 1 amp omega 2 n 1 amp cdots amp omega n n end vmatrix begin vmatrix f omega 1 amp f omega 2 amp cdots amp f omega n omega 1 f omega 1 amp omega 2 f omega 2 amp cdots amp omega n f zeta n vdots amp vdots amp ddots amp vdots omega 1 n 1 f omega 1 amp omega 2 n 1 f omega 2 amp cdots amp omega n n 1 f omega n end vmatrix f w 1 f w 2 f w n 1 1 1 w 1 w 2 w n w 1 n 1 w 2 n 1 w n n 1 displaystyle f omega 1 f omega 2 ldots f omega n cdot begin vmatrix 1 amp 1 amp cdots amp 1 omega 1 amp omega 2 amp cdots amp omega n vdots amp vdots amp ddots amp vdots omega 1 n 1 amp omega 2 n 1 amp cdots amp omega n n 1 end vmatrix Teper skorochuyemo na viznachnik Vandermonda yak nenulovij Rang Rang cirkulyanta C displaystyle C dorivnyuye n d displaystyle n d de d displaystyle d ce stepin gcd f x x n 1 displaystyle gcd f x x n 1 Div takozhCirkulyantnij grafPrimitkiPhilip J Davis Circulant Matrices Wiley New York 1970 ISBN 0471057711 A W Ingleton 1956 The Rank of Circulant Matrices J London Math Soc s1 31 4 445 460 doi 10 1112 jlms s1 31 4 445