Dairesel matris

Doğrusal cebirde, bir dairesel matris her satır vektörü önceki satır vektörüne doğru göreceli bir elemanın döndürüldüğü Toeplitz matrisinin özel bir türüdür.Bir ayrık Fourier dönüşümü ile kösegenlestirilir çünkü sayısal analizde, dairesel matrisler önemlidir,ve dolayısıyla bunları içeren doğrusal denklemler hızlı bir hızlı Fourier dönüşümü kullanarak çözülmüş olabilir.^[1] Onlar siklik grup ${\displaystyle \mathbf {Z} /n\mathbf {Z} }$ üzerinde bir evrişim operatörünün İntegral çekirdeği analitik yorumlanabilir.Kriptografide,dairesel matris gelişmiş şifreleme standardında katışık sütunlar içinde kullanılabilir.

Tanım

Bir ${\displaystyle n\times n}$ dairesel matrisin ${\displaystyle \ C}$ alınan formu

${\displaystyle C={\begin{bmatrix}c_{0}&c_{n-1}&\dots &c_{2}&c_{1}\\c_{1}&c_{0}&c_{n-1}&&c_{2}\\\vdots &c_{1}&c_{0}&\ddots &\vdots \\c_{n-2}&&\ddots &\ddots &c_{n-1}\\c_{n-1}&c_{n-2}&\dots &c_{1}&c_{0}\\\end{bmatrix}}.}$

Bir dairesel matris bir vektör ${\displaystyle \ c}$ tarafından tamamen özeldir,bu ${\displaystyle \ C}$ nin ilk sütunu olarak görünür,${\displaystyle \ C}$ nin kalan sütunları ile bir ${\displaystyle \ c}$ vektörünün sütun indisine eşit dengeli her halkalı permutasyonudür.${\displaystyle \ C}$ nin son satırı ${\displaystyle \ c}$ içinde tersten vektördür,ve geri kalan satırları son satırın her halkalı permutasyonudur.Farklı kaynaklardan katsayılar, birinci satır yerine matrisin ilk sütun karşılık gelen ya da kaymanın farklı bir yönü ile, örneğin, farklı şekillerde de dairesel matris tanımlar unutmayın.

Polinom ${\displaystyle f(x)=c_{0}+c_{1}x+\dots +c_{n-1}x^{n-1}}$ matris ${\displaystyle C}$ nin ilişkili polinomu olarak adlandırılır.

Özellikler

Özvektörler ve özdeğerler

Bir dairesel matrisin özvektörü aşağıdaki ile verilir

${\displaystyle v_{j}=(1,~\omega _{j},~\omega _{j}^{2},~\ldots ,~\omega _{j}^{n-1})^{T},\quad j=0,1,\ldots ,n-1,}$

burada ${\displaystyle \omega _{j}=\exp \left({\tfrac {2\pi ij}{n}}\right)}$ n-inci birimin kökleri ve ${\displaystyle i={\sqrt {-1}}}$ sanal birim'dir.

Özdeğerlerin karşılığı ise şöyle verilir

${\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.}$

Determinant

Yukardaki özdeğer için açık formülün bir sonucu olarak, dairesel matrisin determinantı şöyle hesaplanabilir:

${\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}).}$

bir matrisin özdeğeri devrik matrisle değiştirilemiyorsa, bir eşdeğer formulasyon;

${\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}).}$

Rank

Dairesel ${\displaystyle C}$ matrisinin rankı ${\displaystyle n-d}$ ye eşittir, burada ${\displaystyle d}$ ifadesi ${\displaystyle \gcd(f(x),x^{n}-1)}$ in derecesidir.^[2]

Diğer özellikler

• Elimizde

${\displaystyle C=c_{0}I+c_{1}P+c_{2}P^{2}+\ldots +c_{n-1}P^{n-1}=f(P).}$ var

burada P is the 'döngüsel permütasyon' matrisidir, bir özel permütasyon matrisi şöyle verilir

${\displaystyle P={\begin{bmatrix}0&0&\ldots &0&1\\1&0&\ldots &0&0\\0&\ddots &\ddots &\vdots &\vdots \\\vdots &\ddots &\ddots &0&0\\0&\ldots &0&1&0\end{bmatrix}}.}$

• ${\displaystyle n\times n}$ in kümesi bir n-boyutlu vektör uzayının dairesel matrisli formu; bu dairesel grupun fonksiyon uzayı n, ${\displaystyle \mathbf {Z} /n\mathbf {Z} ,}$ nın yerine veya grup halkasına eşdeğerlilik olarak yorumlanabilir.
• Dairesel matrisin bir değişmeli cebir formu ,nedeniyle verilen herhangi iki dairesel matrisin ${\displaystyle \ A}$ and ${\displaystyle \ B}$,toplamı ${\displaystyle \ A+B}$ daireseldir, çarpımı ${\displaystyle \ AB}$ daireseldir, ve ${\displaystyle \ AB=BA}$.
• Verilen boyutta bir dairesel matrisin özvektörleri aynı boyutun birimsel ayrık Fourier dönüşümü matrisinin sütunlarıdır.sonraki matris aşağıdaki ile tanımlanır

${\displaystyle U_{n}={\frac {1}{\sqrt {n}}}F_{n},\quad {\text{burada}}\quad F_{n}=(f_{jk})\quad {\text{ile}}\quad f_{jk}=\mathrm {e} ^{-2jk\pi \mathrm {i} /n},\quad {\text{için}}\quad 0\leq j,k<n.}$

Böylece, ${\displaystyle U_{n}}$ matris C ile köşegenleştirilmiştir,aslında elimizde

${\displaystyle C=U_{n}^{*}\operatorname {diag} (F_{n}c)U_{n}={\frac {1}{n}}F_{n}^{*}\operatorname {diag} (F_{n}c)F_{n},}$

var

burada ${\displaystyle c\!\,}$ ifadesi ${\displaystyle C\,\!}$nin ilk sütunudur. Böylece,${\displaystyle C}$ nin özdeğeri${\displaystyle \ F_{n}c}$ çarpımı ile verilir.Bu çarpım bir Hızlı Fourier dönüşümü tarafından kolayca hesaplanabilir .^[3]

Analitik yorumlama

Ayrık Fourier dönüşümü ile bağlantısı açıklanarak,dairesel matrisler geometrik olarak yorumlanabilir

${\displaystyle \mathbf {R} ^{n}}$ içinde düşünülen vektörler as fonksiyonlar olarak tamsayılar ile periyodu n, (yani periyodik çift-sonsuz dizisi olarak: ${\displaystyle \dots ,a_{0},a_{1},\dots ,a_{n-1},a_{0},a_{1},\dots }$) veya eşdeğerliliği,fonksiyon olarak n,sıranın döngüsel grubudur (${\displaystyle C_{n}}$ veya ${\displaystyle \mathbf {Z} /n\mathbf {Z} }$) geometrikseldir,(köşelerin) düzgün n-gon olarak:bu periyodik fonksiyonlara bir ayrık analog olarak gerçek çizgi ya da dairedir.

Eğer öyleyse, operator teorisinin bakışından, bir dairesel matris bir ayrık integral dönüşümünün çekirdeğidir, yani ${\displaystyle (c_{0},c_{1},\dots ,c_{n-1})}$ fonksiyonunun evrişim operatörü için; bu bir ayrık dairesel evrişimdir.Formül için ${\displaystyle (b_{i}):=(c_{i})*(a_{i})}$ fonksiyonunun evrişimi

${\displaystyle b_{k}=\sum _{i=0}^{n-1}a_{i}c_{k-i}}$ (yerine konan periyodiktir)

dairesel matris ile ${\displaystyle a_{i}}$ vektörünün çarpımıdır . Ayrık Fourier dönüşümünde ise dönüştürülen evrişim çarpmadadır,matris penceresinde köşegenleştirmeye karşı gelir.

Uygulamalar

Doğrusal denklemlerde

Verilen bir matris denklemi

${\displaystyle \ \mathbf {C} \mathbf {x} =\mathbf {b} ,}$

Burada ${\displaystyle \ C}$ bir dairesel kare matris ${\displaystyle \ n}$ in boyutunu dairesel evrişim denklemi olarak yazabiliriz

${\displaystyle \ \mathbf {c} \star \mathbf {x} =\mathbf {b} ,}$

Burada ${\displaystyle \ c}$ ifadesi ${\displaystyle \ C}$ nin ilk sütunudur, ve ${\displaystyle \ c}$ vektörleri, ${\displaystyle \ x}$ ve ${\displaystyle \ b}$ her yön içinde döngüsel genişletilmiştir.dairesel evrişim teoreminin sonuçları kullanılıyor, akıllı-eklenti çarpımı içinde dairesel evrişim dönüşümüne ayrık Fourier dönüşümü kullanabiliriz

${\displaystyle \ {\mathcal {F}}_{n}(\mathbf {c} \star \mathbf {x} )={\mathcal {F}}_{n}(\mathbf {c} ){\mathcal {F}}_{n}(\mathbf {x} )={\mathcal {F}}_{n}(\mathbf {b} )}$

böylece

${\displaystyle \ \mathbf {x} ={\mathcal {F}}_{n}^{-1}\left[\left({\frac {({\mathcal {F}}_{n}(\mathbf {b} ))_{\nu }}{({\mathcal {F}}_{n}(\mathbf {c} ))_{\nu }}}\right)_{\nu \in \mathbf {Z} }\right]^{T}.}$

Bu algoritma özellikle eğer bir hızlı Fourier dönüşümü kullanılıyorsa çok daha hızlı standard Gauss elemesidir,.

Çizge kuramında

Çizge kuramında graf ya da digrafın komşuluk matrisi daireseldir dairesel graf (veya digraf) denir.Onun otomorfizm grubu, tam uzunlukta döngü içeriyorsa eşdeğeri bir graftır daireseldir.Möbiüs merdiveni dairesel graflara örnekleridir,yanı sıra asal düzenin alanları için Paley grafları vardır

Kaynakça

1. Davis, Philip J., Circulant Matrices, Wiley, New York, 1970 ISBN 0471057711
2. 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. 
3. Golub, Gene H.; Van Loan, Charles F. (1996), "§4.7.7 Circulant Systems", Matrix Computations (3rd bas.), Johns Hopkins, ISBN 978-0-8018-5414-9 

Dış bağlantılar

• R. M. Gray, Toeplitz and Circulant Matrices: A Review
• Eric W. Weisstein, Dairesel matris (MathWorld)

Şablon:Numerical linear algebra