Національна Академія Наук України

Фізико-технічний інститут низьких температур

ім. Б.І. Вєркіна

Венгеровський Валентин Валентинович

УДК 519.177

АСИМПТОТИЧНІ ВЛАСТИВОСТІ СПЕКТРА

ВИПАДКОВИХ РОЗРІДЖЕНИХ МАТРИЦЬ

01.01.03 -- математична фізика

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня

кандидата фізико-математичних наук

Харків -- 2007

Дисертацією є рукопис.

Робота виконана у Фізико-технічному інституті низьких температур ім. Б.І. Вєркіна НАН України.

Науковий керівник:

доктор фізико-математичних наук, старший науковий співробітник

Щербина Марія Володимирівна

Фізико-технічний інститут низьких температур ім. Б.І. Вєркіна НАН

України, м. Харків, завідувач відділу статистичних методів

математичної фізики.

Офіційні опоненти:

доктор фізико-математичних наук, професор, академік НАН України

Пастур Леонід Андрійович

Фізико-технічний інститут низьких температур ім. Б.І. Вєркіна НАН

України, завідувач відділу теоретичної фізики; кандидат фізико-математичних наук, доцент

Ільїнський Олександр Іванович

Харківський національний університет ім. В.Н. Каразіна, м. Харків,

доцент кафедри функцій та функціанального аналізу.

Провідна установа: Інститут математики НАН України, м. Київ, відділ математичної фізики.

Захист відбудеться "__ " ________ 2007 р. о ___ на засіданні спеціалізованої вченої ради Д 64.175.01 у Фізико-технічному інституті низьких температур імені Б.І. Вєркіна НАН України за адресою: 61103, м. Харків, пр. Леніна, 47.

З дисертацією можна ознайомитись у науковій бібліотеці Фізико-технічного інституту низьких температур ім. Б.І. Вєркіна НАН України, м. Харків, пр. Леніна, 47. Автореферат розісланий "__" ______ 2007 р.

Вчений секретар

Спеціалізованої вченої ради Горькавий В.О.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Після піонерської роботи Ю. Вігнера почалося інтенсивне вивчення асимптотичних спектральних властивостей різноманітних ансамблів випадкових матриць. В наш час теорія випадкових матриць застосовується в численних галузях математики та фізики.

Найбільше вивченим є вігнеровський ансамбль випадкових матриць. У роботах Ю. Вігнера, М. Мети, Л. Арнольда, Л. Пастура, В. Гірка, Я. Сіная, О. Сошнікова та інших були розглянуті основні питання, пов'язані з так званим глобальним режимом для цього ансамблю, деякі питання про край спектра і спектральну норму. З подальшим розвитком науки з'явилися нові цікаві ансамблі.

В останні десятиріччя для моделювання таких систем як інтернет, співтовариство вчених, харчові ланцюги у біології, моделі спінових стекол у фізиці, комбінаторній оптимізації та інших були запроваджені нові ансамблі випадкових матриць. Матриці у цих моделях суттєво відрізняються від ансамблю Вігнера. Ці ансамблі були вивчені чисельно та на фізичному рівні строгості.

У дисертації вивчаються ансамблі зважених матриць суміжності для випадкового розрідженого графа, зважених операторів Лапласа на випадковому розрідженому графі, регуляризованих перехідних ймовірностей випадкового розрідженого графа. Данні ансамблі є маловивченими і тому дослідження їх асимптотичних спектральних властивостей є актуальним.

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційне дослідження проводилося у відділі статистичних методів математичної фізики математичного відділення Фізико-технічного інституту низьких температур ім. Б.І. Вєркіна НАН України. Напрямок досліджень передбачений тематичним планом наукової праці ФТІНТ по темі: "Асимптотичні властивості функцій великого числа змінних у математичній фізиці", державний реєстраційний номер 0103U000315.

Мета і задачі дослідження. Метою дисертаційної роботи є аналіз асимптотичних спектральних властивостей ансамблю зважених розріджених матриць суміжності, ансамблю зважених операторів Лапласа на випадкових розріджених графах з випадковою вагою, ансамблю регуляризованих матриць перехідних ймовірностей випадкових розріджених графів.

Для досягнення цієї мети передбачається розв'язати наступні задачі:

1) вивести системи рекурентних співвідношень, за допомогою яких можна знайти граничні моменти та умови на моменти ваги, достатні для виконання умови єдиності відновлювання граничної міри, для ансамблів випадкових зважених матриць суміжності, зважених операторів Лапласа на випадкових графах з випадковою вагою, спрощених регулярізованих матриць перехідних ймовірностей випадкових графів;

2) вивести систему рекурентних співвідношень, за допомогою якої можна знайти головний член асимптотики кореляторів моментів ансамблю випадкових зважених матриць суміжності;

3) довести слабку збіжність за ймовірністю нормованих рахуючих мір та знайти граничне перетворення Стілтьєса для ансамблів випадкових зважених матриць суміжності, операторів Лапласа на випадкових графах з випадковою вагою, регуляризованих матриць перехідних імовірностей випадкових графів;

4) довести необмеженість спектра у випадку ансамблю зважених матриць суміжності та у випадку оператора Лапласа з невід'ємною вагою й отримати явний вид граничної міри для випадку випадкових в зважених матриць суміжності, коли ;

5) довести слабку збіжність за ймовірністю нормованих рахуючих мір ансамблів випадкових зважених матриць суміжності, операторів Лапласа на випадкових графах з випадковою вагою і знайти граничні міри для випадку .

Об'єкт дослідження. Ансамблі випадкових зважених матриць суміжності, операторів Лапласа на випадкових графах з випадковою вагою, регуляризованих матриць перехідних ймовірностей випадкових графів.

Предмет дослідження. Асимптотичні властивості нормованих рахуючих мір ансамблів випадкових матриць суміжності, операторів Лапласа на випадкових графах з випадковою вагою, регуляризованих матриць перехідних ймовірностей випадкових графів.

Методи дослідження. Застосовується ідея Вігнера для комбінаторного зображання моментів і метод перетворень Стілтьєса.

Наукова новизна одержаних результатів. У дисертаційній роботі вперше вивчалися вищезгадані ансамблі. Були отримані наступні нові результати:

1) отримано системи рекурентних співвідношень, які дозволяють знайти граничні моменти й умови на моменти ваги, достатні для виконання умови єдиності відновлювання граничної міри, для ансамблів випадкових зважених матриць суміжності, операторів Лапласа на випадкових графах з випадковою вагою, спрощених регуляризованих матриць перехідних ймовірностей випадкових графів;

2) отримано систему співвідношень, яка дозволяє знайти головні члени асимптотики кореляторів моментів ансамблю випадкових зважених матриць суміжності;

3) доведена слабка збіжність за ймовірністю нормованих рахуючих мір та знайдено граничне перетворення Стілтьєса для ансамблів випадкових зважених матриць суміжності, операторів Лапласа на випадкових графах з випадковою вагою, регуляризованих матриць перехідних ймовірностей випадкових графів;

4) доведена необмеженість спектра у випадку ансамблю випадкових зважених матриць суміжності та випадку оператора Лапласа з невід'ємною вагою і отримати явний вид граничної міри для випадку випадкових зважених матриць суміжності, коли ;

5) доведена слабка збіжність за ймовірністю нормованих рахуючих мір ансамблів випадкових зважених матриць суміжності, операторів Лапласа на випадкових графах з випадковою вагою і знайдено граничні міри для випадку .

Практичне значення одержаних результатів. Дисертація має теоретичний характер. Методи, які були розвинуті у цій роботі, можуть слугувати основою для дослідження інших ансамблів ермітових випадкових матриць зі слабо залежними елементами.

Особистий вклад здобувача. Усі результати, представлені на захист, отримані автором. У статті [] постановка задач належить О. М. Хорунжому та М.В. Щербині.

Апробація результатів дисертації. Результати дисертації доповідались та обговорювались на Міжнародній конференції "Конференція з опуклої геометрії та явища великих вимірностей" (м. Відень, 2005), на Міжнародній конференції "Каразінські читання" (м. Харків, 2004), на семінарі математичного відділення Фізико-технічного інституту низьких температур ім. Б.І. Вєркіна НАН України (керівник -- Є.Я. Хруслов), на семінарі відділу статистичних методів математичного відділення Фізико-технічного інституту низьких температур ім. Б.І. Вєркіна НАН України (керівник -- Л.А. Пастур).

Публікації. Основні результати дисертації опубліковані у 6 роботах [1,5,2,6,3,4], з яких 4 статті у наукових виданнях, які включені до переліку ВАК України, та 2 роботи у тезах конференції, з них 5 робіт без співавторів.

Структура дисертації. Дисертація складається зі вступу, чотирьох розділів, додатку, висновків та списку використаних джерел, що включає 70 найменувань і займає 7 сторінок. Загальний обсяг роботи становить 134 сторінок. Результати роботи, які представлені до захисту, сформульовані та доведені у розділах 2--5.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі обгрунтовується актуальність теми дисертації, ступінь її наукової розробки, мета і задачі, предмет і об'єкт дослідження, наукова новизна, методологічна база роботи.

У першому розділі роботи розкриваються базові визначення, які використані у наступних розділах, та розглядаються близькі за тематикою роботи інших авторів.

Результати дисертаційної роботи наведено у другому, третьому, четвертому та п'ятому розділах.

У другому розділі за допомогою методу моментів з'ясовуються основні асимптотичні спектральні властивості вищезгаданих ансамблів.

У підрозділі 2.1 розглядається випадок зваженої матриці суміжності.

Нехай --- ймовірнісний простір. І нехай є сім'я однаково розподілених незалежних в сукупності випадкових величин . Означимо . Зараз для кожній пари натуральних чисел визначена випадкова величина . Для довільної пари чисел , визначимо сім'ю однаково розподілених незалежних у сукупності випадкових величин, яке незалежне від першого,

()

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

()

Нормована рахуюча функція власних значень позначається Також позначимо -ий момент цієї випадкової функції розподілу та його математичне сподівання

Метод моментів вимагає існування усіх моментів

()

Основним результатом підрозділу є наступна теорема:

Теорема 2. При виконанні умови

()

міра слабко збігається за ймовірністю до невипадкової імовірнісної міри ,

()

яка однозначно визначається моментами, котрі дорівнюють

()

де числа визначаються системою рекурентних співвідношень

()

з початковою умовою

()

Позначимо корелятор через

Теорема 2.1 є наслідком наступної Теореми 2.2.

Теорема .2 При виконанні умови () Теореми 2.1

(i) Границя кореляторів дорівнює нулю

()

(ii) Для довільного існує границя моментів

()

де числа визначаються системою рекурентних співвідношень () з початковою умовою (),

References

[] Khorunzhy O., Shcherbina M., and Vengerovsky V. Eigenvalue distribution of large weighted random graphs // J. Math. Phys. - 2004. - Vol. 45. No. 4. - P. 1648-1672.

[] Венгеровский В. Асимптотика коррелятора ансамбля разреженных случайных матриц // Математическая физика, анализ, геометрия. - 2004. - Т. 11, 2. - Стр. 135-160.

[] Венгеровский В. Распределение собственных значений ансамбля разбавленных матриц с зависимыми элементами, возникающего в теории графов // Журнал математической физики, анализа, геометрии. - 2005. - Т. 1, 1. - Стр. 35-52.

[] Венгеровский В. Предел моментов спектральной плотности некоторого ансамбля разбавленных случайных матриц с зависимыми элементами // Доповіді національної академії наук України. - 2005. - 9. - Стр. 7-12.

[] Vengerovsky V. Eigenvalue Distributions of Large Weighted Random Matrices // Mathematical Symposium "First Karazin Scientific Readings". - Kharkov. - 2004. - P. 42.

[] Vengerovskyi V. Eigenvalue distributions of some ensembles of sparse random matrices // Conference of Convex Geometry and High Dimensional Phenomena. - Wien. - 2005. - P. 49.

ВИСНОВКИ

У висновках підбиваються підсумки проведеного дослідження, наведено отримані у роботі нові результати про ансамблі випадкових розріджених матриць, а саме:

* Встановлені системи рекурентних співвідношень, за допомогою яких можна знайти граничні моменти та умови на моменти ваги, достатні для виконання умови єдиності відновлювання граничної міри, для ансамблів випадкових зважених матриць суміжності, зважених операторів Лапласа на випадкових графах з випадковою вагою, спрощених регуляризованих матриць перехідних імовірностей випадкових графів.

* Встановлена система рекурентних співвідношень, за допомогою якої можна знайти головний член асимптотики кореляторів моментів ансамблю випадкових зважених матриць суміжності.

* Доведена слабка збіжність за ймовірністю нормованих рахуючих мір та знайдено граничне перетворення Стілтьєса для ансамблів випадкових зважених матриць суміжності, операторів Лапласа на випадкових графах з випадковою вагою, регуляризованих матриць перехідних імовірностей випадкових графів.

* Доведено необмеженість спектра у випадку ансамблю випадкових зважених матриць суміжності та у випадку ансамблю операторів Лапласа на випадкових графах з невід'ємною вагою й отримано явний від граничної міри для випадку випадкових зважених матриць суміжності, коли .

* Доведена слабка збіжність за ймовірністю нормованих рахуючих мір ансамблів випадкових зважених матриць суміжності, операторів Лапласа на випадкових графах з випадковою вагою і знайдено граничні міри для випадку .

АНОТАЦІЯ

Венгеровський В.В. Асимптотичні властивості спектра випадкових розріджених матриць. -- Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.01.03 -- математична фізика. Фізико-технічний інститут низьких температур ім. Б.І. Вєркіна, Харків, 2006.

Дисертація присвячена асимптотичних спектральних властивостей ансамблю зважених розріджених матриць суміжності, ансамблю зважених операторів Лапласа на випадкових розріджених графах з випадковою вагою, ансамблю регуляризованих матриць перехідних ймовірностей випадкових розріджених графів за допомогою методу моментів та методу перетворень Стілтьєса.

Доведена слабка збіжність за ймовірністю нормованих рахуючих мір ансамблів випадкових зважених матриць суміжності, операторів Лапласа на випадкових графах з випадковою вагою, регуляризованих матриць перехідних ймовірностей випадкових графів при фіксованому параметрі . Виражено граничні перетворення Стілтьєса. Отримано системи рекурентних співвідношень, які дозволяють знайти граничні моменти і умови на моменти ваги для виконання достатньої умови єдиність відновлення граничної міри. Доведена необмеженість спектра у випадку ансамблю випадкових зважених матриць суміжності і отримано явний вид граничної міри для випадку . Знайдено явний вид граничні міри для випадку . Отримано систему співвідношень, яка дозволяє знайти головні члени асимптотики кореляторів моментів ансамблю випадкових зважених матриць суміжності.

Ключові слова: розріджені матриці, нормована рахуюча міра, матриця суміжності, оператор Лапласа, матриця перехідних ймовірностей, перетворення Стілтьєса.

АННОТАЦИЯ

Венгеровский В.В. Асимптотические свойства спектра случайных разреженных матриц. -- Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.01.03 -- математическая физика. Физико-технический институт низких температур им. Б.И. Веркина, Харьков, 2006.

Диссертация посвящена исследованию асимптотических спектральных

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

Спектральные свойства ансамблей случайных разреженных матриц являются мало изученными, в отличие от аналогичных свойств больших графов с регулярной структурой. Интерес к подобным ансамблям инспирирован изучением реальных больших систем. У матрицы в этих ансамблях лишь небольшое число элементов в каждой строке отлично от нуля и элементы не сосредоточены возле главной диагонали, а выбираются случайным образом. Ожидалось, что свойства будут существенно отличаться от свойств известных ансамблей, например, от ансамбля Вигнера. Некоторые из подансамблей ранее изучались численно и математически некорректными методами реплик и суперсимметрии. В физике такие ансамбли используются для построения теории среднего поля андерсоновской локализации перехода металл-диэлектрик для модели неупорядоченного проводника с малым количеством связей в бесконечномерном случае. В данной диссертации математически строго изучаются обобщенные ансамбли.

Во втором разделе методом моментов изучаются три ансамбля случайных матриц. Это ансамбли взвешенных матриц смежности, операторов Лапласа на графе и упрощенный вариант матриц переходных вероятностей. Доказывается, что дисперсии моментов стремятся к нулю. Найдены системы рекуррентных соотношений, из которых однозначно определяются предельные моменты. Получены достаточные условия на рост моментов для однозначного определения предельной меры по ее моментам. Для этого, кроме существования всех моментов, требуется ограничение роста моментов типа условия Карлемана.

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

В четвертом разделе применяется резольвентный метод. При существенно меньших ограничениях (требуется лишь существование 4-го момента веса) решаются задачи для ансамбля взвешенных матриц смежности, ансамбля взвешенных операторов Лапласа на графе и нерешаемая методом моментов задача о регуляризованной матрице переходных вероятностей. Для каждого случая доказано стремление к нулю дисперсии преобразования Стилтьеса, найдено свое функциональное уравнение для определенной производящей функции, имеющее единственное решение в некотором пространстве. Через это решение выражено предельное преобразование Стилтьеса. Для случая ансамбля регуляризованных матриц переходных вероятностей случайного разреженного графа метод требуется модифицировать, так как элементы соответствующей матрицы являются зависимыми. В случае невзвешенной матрицы смежности для найдено разложение преобразования Стилтьеса в абсолютно сходящийся ряд по . Предельная мера является чисто точечной и выражена через нормированные считающие меры конечных деревьев. Следует также отметить, что в данном случае носитель меры неограничен, что является нехарактерным для оператора Лапласа.

Полученные функциональные уравнения сложны для анализа, поэтому трудно извлечь информацию о свойствах предельной меры. Например, не удается доказать, что для матрицы смежности при предельная мера содержит абсолютно непрерывную компоненту, хотя это кажется весьма вероятным. Некоторую информацию дает предельный переход . В пятом разделе исследован предельный переход для матрицы смежности и предельный переход для оператора Лапласа на случайном графе. Показывается, что в пределе будут выполняться полукруговой закон и деформированный полукруговой закон.

Ключевые слова: разреженные матрицы, нормированная считающая мера, матрица смежности, оператор Лапласа, матрица переходных вероятностей, преобразование Стилтьеса.

ABSTRACT

Vengerovsky V.V. Asymptotic properties of spectra of sparse random matrices. -- Manuscript.

Thesis for obtaining the degree of candidate of sciences in physics and mathematics by speciality 01.01.03 -- mathematical physics. B. Verkin Institute for Low Temperature Physics and Engineering of National Academy of Sciences of Ukraine, Kharkіv, 2006.

The thesis is devoted to the analysis of asymptotic properties of the spectra of ensembles of sparse random weighted adjacency matrices, Laplace operators, and matrices of transition probabilities. The weak convergence is proved of the normalized counting measure for ensembles of sparse random weighted adjacency matrices, Laplace operators, and matrices of transition probabilities with fixed parameter p. The Stieltes transforms of limiting measures are expressed. A system of recurrent relations is found that let us get an explicit expression of every limiting moments. Sufficient conditions were also found for moments of weight for the uniqueness of determining of the limiting measure by moments. It is proved that the spectrum of the ensemble of the sparse random weighted adjacency matrices with the parameter is unbounded. An explicit expression of the limiting measures is found for the case . A system of recurrent relations is found that let us possible to determine the main asymptotic coefficients of correlators of moments for the case of ensembles of the sparse random weighted adjacency matrices.

Key words: sparse random matrices, normalized counting function, adjacency matrix, Laplace operator, matrix of probabilities of transition, Stieltjes transform.