Введение

Прикладную математику можно рассматривать как набор инструментов, позволяющих решать те или иные проблемы, возникающие на практике. В данной статье мы рассмотрим один из таких инструментов — преобразование девиации применительно к анализу матрицы евклидовых расстояний. Спектр результирующей матрицы позволяет судить о размерности исходных данных и рассчитать координаты исходных точек относительно собственного центра координат.

Допустим, у нас имеется n > 2 точек и известны все расстояния между ними. Потенциальная мерность пространства равна n-1. Надо определить, пространству какой мерности принадлежат заданные точки, а также координаты точек в данном пространстве.
Одним из косвенных способов определения мерности пространства на основании расстояний между точками является вычисление определителя Кэли-Менгера (КМ). Однако данный способ малопригоден для анализа пространств большой размерности.

1. Преобразование девиации

Итак, мы имеем на входе некую симметричную матрицу М размерности N с нулевым следом (элементы главной диагонали равны нулю). Нам надо определить преобразование в некоторую новую матрицу U. При этом значения исходной матрицы должны рассчитываться из новой по правилам сложения расстояний:



Тогда значения матрицы M можно выразить через спектр U как взвешенную сумму разности квадратов компонент собственных векторов:


Здесь — набор собственных чисел матрицы U, а k — матрица собственных векторов, соответствующих собственным числам. Длина векторов нормирована к 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.

Движемся дальше. Если точки принадлежат одной прямой, то спектр должен содержать только одно значение.
Рассчитаем значение спектра для трех точек отрезка (две по краям и одна посередине) . Получаем:



Действительно, спектр содержит только одну компоненту. Центроид находится посередине отрезка, как и ожидалось.

Теперь зададим каверзный вопрос — какому пространству принадлежит невозможный треугольник, то есть тот, в котором нарушено неравенство треугольника?


Если спектр содержит отрицательные значения, то это означает, что в евклидовом пространстве набор точек с такими характеристиками реализоваться не может,- координаты точек становятся мнимыми. Можно использовать данное свойство спектра для проверки валидности матрицы расстояний.

Передышка

Сделаем паузу и осмотримся. Мы определили преобразование девиации и применили его к матрице квадратов расстояний. Получившаяся матрица девиации расстояний отражает свойства пространства исходного набора точек.

Численно проверить описанные свойства для матриц небольшого размера можно в интерактивном режиме, используя электронные таблицы и сервис wolframalpha для расчета собственных значений/векторов.

Если не будет больших возражений, то в следующей статье мы продолжим рассмотрение спектральных свойств некоторых стандартных наборов геометрических точек — решеток, фигур, линий, а также посмотрим на спектры наборов из фигур.

Продолжение...