Введення
Прикладна математика це набір інструментів, що дозволяють вирішувати ті чи інші проблеми, що виникають на практиці. У цій статті розглянемо один з таких інструментів - перетворення девіації стосовно матриці євклідових відстаней. Спектр отриманої в результаті матриці Гріна дозволяє судити про розмірність вихідних даних і розрахувати координати вихідних точок щодо власного центру координат.
Припустимо, у нас є (n > 2) точок і відомі всі відстані між ними. Потенційна мірність простору дорівнює (n-1). Треба визначити, простору якої мірності належать задані точки, а також координати точок в даному просторі.
1. Перетворення девіації
Нехай задана якась симетричну матрицю М розмірності N з нульовим слідом (елементи головної діагоналі дорівнюють нулю). Нам треба визначити перетворення на деяку нову матрицю U. При цьому значення вихідної матриці повинні розраховуватися з нової за правилами складання відстаней:
Тоді значення матриці M можна виразити через спектр U як зважену суму різниці квадратів компонент власних векторів:
Тут - набір власних чисел матриці U, а - матриця власних векторів, що відповідають власним числам. Довжина векторів нормована до 1.
Загальним видом матриці U, що задовольняє умову (1.1), є вираз:
Тут довільний вектор, а довільна константа. Для визначення даних величин необхідно встановити додаткові умови. Такою умовою є вимога лапласіаноподібності матриці U. У матриці лапласіана елементи головної діагоналі дорівнюють сумі елементів відповідного стовпчика (рядка) зі зворотним знаком:
Підставляючи (1.3) в (1.4) з урахуванням симетрії M, отримуємо тотожність:
з якого визначаємо шукані вирази для вектора і константи:
Таким чином вектором в (1.3) є вектор середніх значень рядка (стовпчика) вихідної матриці (в термінах графів - середня кардинальність/ступінь вершини графа), а константою - середнє значення матриці в цілому (середній ступінь вершин всього графа):
Перетворення (1.3) називає перетворенням девіації, оскільки воно відображає відхилення (девіацію) значень вихідної матриці від середніх значень. Результат перетворення будемо називати матрицею девіації.
2. Властивості матриці девіації
Матриця є виродженою (нульовий детермінант і одне з власних значень) - наслідок вимоги лапласіановості.
Елементи головної діагоналі девіації відображають середні значення вихідної матриці:
Слід девіації пов'язаний із середнім значенням вихідної матриці і може бути виражений через суму власних значень:
Твір власних чисел пропорційний потенціалу девіації - ненульовому мінору матриці:
Девіація є обратимою. На підставі матриці девіації можна відновити вихідну:
3. Матриця Гріна, власна система координат
Розгляньмо застосування перетворення девіації до матриці євклідових відстаней. Нехай задано багато точок з відомими відстанями між будь-якою парою. Визначимо мірність простору, якому належать точки та їх координати в даному просторі.
Вихідний набір відстаней представимо у вигляді симетричної матриці квадратів відстаней між точками. Позначимо цю матрицю як D2, де двійка означає квадрат. Застосування операції девіації до матриці квадратів відстаней дає матрицю Гріна G:
Спектр матриці Гріна має такі властивості:
- Кількість ненульових власних значень (ранг матриці) збігається з мірністю простору, в якому знаходяться вихідні точки.
- Значення власних векторів є координатами точок у новому просторі.
- Симетрія власних значень відображає симетрію взаємного розташування точок.
Таким чином спектр матриці Гріна визначає власну систему координат вихідного набору точок. Вага кожної координати визначається значенням спектра (власним числом). Центр нової системи координат називається центроїдом. На головній діагоналі матриці Гріна розташовані квадрати відстані від центроїду до вершин:
Сума всіх таких відстаней (слід) визначає середній радіус безлічі R2. Цей радіус дорівнює сумі значень спектра і пов'язаний із середнім значенням вихідної матриці відстаней відповідно до формули (2.2):
Центроїд набору мінімізує середній радіус набору. Тобто для будь-якого іншого положення центроїду середній радіус набору буде мати більше значення. Додавання самого центроїду в початковий набір точок не змінює спектр, оскільки центроїд нового набору збігається зі старим.
4. Спектри деяких наборів
Спектри трьох вершин (трикутники)
У нас в руках з'явився молоток. Шукаємо цвяхи.
Для однієї/двох точок будувати матрицю Гріна сенсу особливого немає. Дві нетонароджені точки завжди належать одній прямій, тобто одномірному простору.
А ось для трьох точок вже з'являються варіанти. Найпростіший випадок - вершини рівностороннього трикутника. Якщо довжина сторони дорівнює 1, то матриця Гріна матиме вигляд:
Слід даної матриці дорівнює 1, а потенціал (1/3) ^ 2 - (1/6) ^ 2 = 1/9 - 1/36 = 1/12.
Рахуємо спектр (у дужках наведено квадрати відстаней між точками):
Тут ліворуч показано власні значення спектра, а праворуч - значення векторів (координат).
Бачимо, що:
- Спектр має два значення. Це зрозуміло - невироджений трикутник завжди належить 2-мірному простору (площині).
- Обидва власних значення рівні. Це є наслідком симетрії рівностороннього трикутника.
Перевіримо властивості спектра: сума власних чисел дорівнює 1, твір - 1/2 * 1/2 = 1/4 = 1/12 * 3. Все правильно.
Попутно зауважимо, що спектр трьох вершин пов'язаний з площею утвореного ними трикутника (різновид формули Герону):
Відповідно квадрат площі рівностороннього 1-трикутника дорівнює 3/4 * 1/4 = 3/16.
Рухаємося далі. Якщо точки належать одній прямій, спектр повинен містити лише одне значення.
Розрахуємо значення спектра для трьох точок відрізка (дві по краях і одна посередині). Отримуємо:
Дійсно, спектр містить лише одну компоненту. Центроїд знаходиться посередині відрізка, як і очікувалося.
Поставимо каверзне питання - якому простору належить неможливий трикутник, тобто той, в якому порушено нерівність трикутника?
Відповідь очевидна для тих, кому він відомий.
Для «трикутника» спектр складатиметься з двох значень - одне додатне (4.5), а інше від'ємне (-0.833).
Якщо спектр містить від'ємні значення, це означає, що в євклідовому просторі набір точок з такими характеристиками реалізуватися не може, - координати точок стають уявними. Можна використовувати цю властивість спектра для перевірки валідності матриці відстаней.
Перепочинок
Ми визначили перетворення девіації і застосували його до матриці квадратів відстаней. Отримана матриця Гріна відображає властивості простору вихідного набору точок.
Зазначимо, що матриця квадратів відстаней еквівалентна матриці резистивних відстаней. Відповідно матриця Гріна є зворотною матрицею щодо матриці Кірхгофа (лапласіана графа).
У наступній статті продовжимо розгляд спектральних властивостей деяких стандартних наборів геометричних точок - решіток, фігур, ліній, а також подивимося на спектри наборів з фігур.
Продовження...
