Циркулянт

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

У лінійній алгебрі, циркулянт — особливий підвид матриць Тепліца, в якій кожен вектор-стовпчик являє собою попередній вектор стовпчик циклічно зсунутий на один елемент праворуч. У обчислювальній математиці, циклічні матриці важливі, бо воно діагоналізовні за допомогою дискретного перетворення Фур'є, тобто, лінійні рівняння, які містять їх можна розв'язати застосувавши швидке перетворення Фур'є.[1] Їх можна інтерпретувати аналітично як інтегральне ядро згортки циклічної групи тому вони часто з'являються у формальних описах просторово інваріантних лінійних операцій. У криптографії, циклічні матриці використовуються в MixColumns етапі в Advanced Encryption Standard.

Означення[ред.ред. код]

циркулянт має вигляд

Один вектор що з'являється в першому стовпці повністю визначає циркулянт. Інші стовпці є циклічними переставками вектора зі зсувом, що дорівнює індексу стовпця. Останній рядок є вектором у зворотньому порядку, а інші рядки є його циклічними переставками.

Многочлен називається пов'язаним многочленом матриці

Властивості[ред.ред. код]

Власні вектори і значення[ред.ред. код]

Нормалізовані власні вектори циркулянта задаються як

де є nкоренем з одиниці, а це уявна одиниця.

Відповідні власні значення такі

Визначник[ред.ред. код]

Визначник циркулянта можна обчислити як:

Оскільки транспонування не змінює власні значення матриці, то тотожним формулюванням є

Ранг[ред.ред. код]

Ранг циркулянта дорівнює , де це степінь .[2]

Див. також[ред.ред. код]

Циркулянтний граф

Примітки[ред.ред. код]

  1. Philip J. Davis, 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.