Богемские матрицы
Богемская матричная семья [1] представляет собой набор матриц , элементы которых являются членами фиксированного, конечного и дискретного набора, называемого «популяцией». Термин «богемный» впервые был использован для обозначения матриц, элементы которых состоят из целых чисел ограниченной высоты, отсюда и название, происходящее от аббревиатуры BO unded HE ight Matrix of Integers (BOHEMI). [2] Большинство опубликованных исследований этих семейств матриц изучают совокупности целых чисел, хотя это не совсем верно для всех возможных богемских матриц. Единого семейства богемских матриц не существует. Вместо этого можно сказать, что матрица является богемной по отношению к множеству, из которого взяты ее элементы. Богемские матрицы могут обладать дополнительной структурой. Например, это могут быть матрицы Теплица или верхние матрицы Хессенберга .
Приложения
[ редактировать ]Тестирование программного обеспечения
[ редактировать ]Богемские матрицы используются при тестировании программного обеспечения, особенно в линейной алгебры приложениях . Они часто отчетливо представлены на компьютерах. [3] и идентифицируются по экстремальному поведению посредством исчерпывающего поиска (для малых размерностей), случайной выборки или методов оптимизации. Стивен Э. Торнтон использовал эти концепции для разработки инструмента, который решил более двух триллионов проблем собственных значений, выявив случаи сбоя сходимости в некоторых популярных программных системах. [4]
Набор инструментов Anymatrix — это расширяемый инструмент MATLAB матричный , который предоставляет набор отсортированных богемских матриц и утилиты для запросов к этому набору на основе свойств. [5]
Улучшенные границы
[ редактировать ]В презентации на семинаре по богемским матрицам и приложениям 2018 года Ник Хайэм (соавтор набора инструментов Anymatrix) рассказал, как он использовал генетические алгоритмы для богемских матриц с популяцией P = {-1, 0, 1} для уточнения нижних границ максимальный коэффициент роста при развороте ладьи . [6]
Связи с другими областями
[ редактировать ]Случайные матрицы
[ редактировать ]Богемские матрицы можно изучать посредством случайной выборки — процесса, пересекающегося с областью случайных матриц. Однако изучение случайных матриц преимущественно сосредоточено на реальных симметричных или эрмитовых матрицах или матрицах с элементами, полученными из непрерывного распределения, таких как гауссовы ансамбли . Заметными исключениями из этого правила являются работы Теренса Тао и Ван Ву . [7] [8]
Матрицы Бернулли и Адамара.
[ редактировать ]Термин «матрицы Бернулли» иногда используется для описания матриц с элементами, ограниченными ±1 . [9] классифицируя их как богемские матрицы. Матрица Адамара — это матрица Бернулли, которая удовлетворяет дополнительному свойству, а именно тому, что ее определитель максимален. Матрицы Адамара (и матрицы Бернулли) изучаются гораздо дольше, чем существовал термин «богемская матрица». Вопросы, заданные о матрицах Адамара, например вопросы, касающиеся максимальных определителей, могут быть применены и к другим богемским матрицам. Одно из обобщений матриц Адамара включает матрицы Адамара типа Батсона , элементы которых представляют собой корни q- й степени из единицы для q > 2 , и их также можно считать прототипными богемскими матрицами.
Теория графов
[ редактировать ]Матрицы с дискретными элементами, особенно матрицы инцидентности , играют решающую роль в понимании теории графов. Результаты исследований теории графов могут пролить свет на явления, наблюдаемые в экспериментах с богемской матрицей. И наоборот, эксперименты, проводимые с использованием богемских матриц, могут дать ценную информацию о проблемах, связанных с графами. [10]
Комбинаторика
[ редактировать ]Несколько открытых проблем, перечисленных в Энциклопедии целочисленных последовательностей, касающихся богемских матриц, носят комбинаторный характер. Например, в A306782 приведена таблица количества различных минимальных полиномов для матриц Бернулли (богемские матрицы с элементами ±1 ) до размерности 5. Числа для более высоких размерностей остаются неизвестными. Число допустимых матриц Бернулли размерности 6 равно 2. 36 =68 719 476 736 ; хотя это множество можно перебрать исчерпывающе (оно восхитительно параллельно ), более чем экспоненциальный рост числа матриц быстро выходит за пределы численного анализа. Есть симметрии, которыми можно было бы воспользоваться, как это сделано [10] для матриц ноль-единица, но это требует сложных знаний комбинаторики.
Теория чисел
[ редактировать ]Многие теоретики чисел изучали полиномы с ограниченными коэффициентами. Например, полиномы Литтлвуда имеют коэффициенты ±1 в мономиальном базисе. Такие исследователи, как Курт Малер , [11] Эндрю Одлызко , Бьорн Пунен [12] и Питер Борвейн внесли свой вклад в эту область. Используя сопутствующие матрицы , эти полиномиальные задачи с ограниченными коэффициентами можно представить как задачи богемской матрицы. Однако характеристический полином богемской матрицы может иметь коэффициенты, экспоненциально большие по размерности матрицы, поэтому обратное преобразование не всегда применимо. [13] [14]
Связь с магическими квадратами исследуется в Кэтлин Оллереншоу совместно с Д. Бри. книге [15] богемские матрицы явно связаны с квадратичными формами . Более того, в некоторых работах [16]
Решение полиномиальных уравнений
[ редактировать ]Чтобы найти корни многочлена, можно построить соответствующую сопутствующую матрицу и найти ее собственные значения. Эти собственные значения соответствуют корням исходного многочлена. Этот метод обычно используется в полиномиальном пакете NumPy и, как правило, численно стабилен. [17] хотя иногда он может иметь проблемы с полиномами, имеющими большие коэффициенты или плохо обусловленными .
Улучшение этой ситуации включает в себя поиск сопутствующей матрицы минимальной высоты для многочлена в семействе богемских матриц. [18] Однако в настоящее время не известны эффективные методы общего назначения для этого подхода.
История
[ редактировать ]Термин «богемские матрицы» и концепция категоризации проблем таким образом впервые появились в публикации ISSAC в 2016 году. [19] Название произошло от мнемонической матрицы целых чисел Bounded HEight (BOHEMI), хотя с тех пор классификация была расширена и теперь включает в себя другие дискретные группы населения. [20] например, гауссовы целые числа . Полезность и масштабы этой классификации становятся все более признанными после появления первой значимой журнальной публикации. [21] после более мелких более ранних публикаций. По состоянию на март 2022 года в нескольких публикациях явно используется термин «богемские матрицы» в дополнение к уже упомянутым в этой статье. [22] [23] [24]
прошел первый семинар по богемским матрицам В 2018 году в Манчестерском университете под названием «Богемские матрицы и приложения». Эта концепция сродни специализации, предложенной Джорджем Полиа , под названием «Богемские матрицы и приложения». Эта концепция сродни специализации, предложенной полиномом Литтлвуда .
Эта концепция имеет сходство с матрицами шаблонов знаков , где две матрицы с реальными записями считаются эквивалентными, если соответствующие записи имеют одинаковый знак. [25] Богемная матрица с численностью населения P = {-1, 0, 1} является примером матрицы шаблонов знаков и соответствует определенным свойствам, но может также демонстрировать уникальные характеристики, характерные для ее богемной природы.
Ссылки
[ редактировать ]- ^ Хайэм, Николас Дж. (декабрь 2018 г.). «Восхищение богемскими матрицами» . Общество промышленной и прикладной математики. Архивировано из оригинала 28 февраля 2022 года . Проверено 1 марта 2022 г.
- ^ Корлесс, Роберт; Лабан, Джордж; Пипони, Дэн; Рафии Севери, Лейли (5 июля 2022 г.). «Богемская матричная геометрия» . Материалы Международного симпозиума по символьным и алгебраическим вычислениям 2022 года . ИССАК '22. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники: 361–370. arXiv : 2202.07769 . дои : 10.1145/3476446.3536177 . ISBN 978-1-4503-8688-3 .
- ^ Хайэм, Николас Дж. «Богемские матрицы в числовой линейной алгебре» (PDF) . Ник Хайэм — Конференции . Архивировано из оригинала (PDF) 13 ноября 2020 года . Проверено 2 марта 2022 г.
- ^ Торнтон, Стивен Э. (апрель 2019 г.). Алгоритмы для богемских матриц (кандидатская диссертация). Западный университет. Архивировано из оригинала 7 марта 2022 года . Проверено 1 марта 2022 г.
- ^ Микайтис, Мантас; Хайэм, Николас Дж. (31 марта 2021 г.). «любая матрица» . Проверено 29 июня 2024 г.
- ^ Хайэм, Николас Дж. «Богемские матрицы в числовой линейной алгебре» (PDF) . Ник Хайэм — Конференции . Архивировано из оригинала (PDF) 13 ноября 2020 года . Проверено 2 марта 2022 г.
- ^ Тао, Теренс; Ву, Ван (январь 2006 г.). «О случайных матрицах ±1: особенность и определитель» . Случайные структуры и алгоритмы . 28 (1): 1–23. arXiv : math/0411095 . дои : 10.1002/rsa.20109 . S2CID 5361802 . Проверено 2 марта 2022 г.
- ^ Ву, Ван (2008). «Случайные дискретные матрицы». Горизонты комбинаторики . Общество математических исследований Боляи. Том. 17. С. 257–289. arXiv : math/0611321 . дои : 10.1007/978-3-540-77200-2_13 . ISBN 978-3-540-77199-9 . S2CID 118703720 .
- ^ Тао, Теренс; Ву, Ван (январь 2006 г.). «О случайных матрицах ±1: особенность и определитель» . Случайные структуры и алгоритмы . 28 (1): 1–23. arXiv : math/0411095 . дои : 10.1002/rsa.20109 . S2CID 5361802 . Проверено 2 марта 2022 г.
- ^ Jump up to: Перейти обратно: а б Живкович, Миодраг (2006). «Классификация малых (0,1) матриц» . Линейная алгебра и ее приложения . 414 (1): 310–346. arXiv : math/0511636 . дои : 10.1016/j.laa.2005.10.010 .
- ^ Малер, Курт (1963). «О двух экстремальных свойствах многочленов» . Иллинойсский математический журнал . 7 (4): 681–701. дои : 10.1215/ijm/1255645104 . S2CID 118793107 .
- ^ Одлызко, Андрей (сентябрь 1992 г.). «Нули полиномов с коэффициентами 0,1». Семинар по алгоритмам : 169. CiteSeerX 10.1.1.47.9327 .
- ^ Борвейн, Питер Б.; Йоргенсон, Локи (декабрь 2001 г.). «Видимые структуры в теории чисел» . Американский математический ежемесячник . 108 (10): 897–910. дои : 10.1080/00029890.2001.11919824 . JSTOR 2695413 . S2CID 454318 . Проверено 3 марта 2022 г.
- ^ Калкин, Нил Дж ; Чан, Юнис Ю.С.; Корлесс, Роберт М. (2 июня 2021 г.). «Некоторые факты и предположения о полиномах Мандельброта» . Кленовые транзакции . 1 (1): 13. дои : 10.5206/mt.v1i1.14037 . S2CID 242158547 .
- ^ Оллереншоу, Кэтлин; Бри, Д. (1998). Наиболее совершенные пандиагональные магические квадраты . ИМА.
- ^ Хайэм, Николас Дж; Леттингтон, Мэтью (2022). «Оптимизация и факторизация матрицы Вильсона» . Американский математический ежемесячник . 129 (5): 454–465. дои : 10.1080/00029890.2022.2038006 . S2CID 233322415 . Архивировано из оригинала 3 марта 2022 года . Проверено 3 марта 2022 г.
- ^ Эдельман, Алан; Мураками, Х. (апрель 1995 г.). «Полиномиальные корни из собственных значений сопутствующей матрицы» (PDF) . Математика вычислений . 64 (210): 763–776. Бибкод : 1995MaCom..64..763E . дои : 10.1090/S0025-5718-1995-1262279-2 . Архивировано (PDF) из оригинала 24 января 2022 года . Проверено 2 марта 2022 г.
- ^ Чан, Юнис Ю.С.; Корлесс, Роберт М. (6 февраля 2017 г.). «Новый вид матрицы-компаньона» . Электронный журнал линейной алгебры . 32 : 335–342. дои : 10.13001/1081-3810.3400 .
- ^ Корлесс, Роберт М.; Торнтон, Стивен Э. (2017). «Богемский проект собственных значений» . ACM-коммуникации в компьютерной алгебре . 50 (4): 158–160. дои : 10.1145/3055282.3055289 . S2CID 34583673 . Архивировано из оригинала 1 марта 2022 года . Проверено 28 февраля 2022 г.
- ^ Корлесс, Роберт (2 июня 2021 г.). «Чему мы можем научиться из богемских матриц» . Кленовые транзакции . 1 (1). дои : 10.5206/mt.v1i1.14039 . S2CID 241595165 .
- ^ Чан, Юнис Ю.С.; Корлесс, Роберт М.; Гонсалес-Вега, Лауреано; Сендра, Дж. Рафаэль; Сендра, Хуана; Торнтон, Стивен Э. (сентябрь 2020 г.). «Верхнегессенбергская и теплицкая богема» . Линейная алгебра и ее приложения . 601 : 72–100. arXiv : 1907.10677 . дои : 10.1016/j.laa.2020.03.037 . S2CID 198899515 . Архивировано из оригинала 13 августа 2023 года . Проверено 3 марта 2022 г.
- ^ Фаси, Массимилиано; Негри Порцио, Джан Мария (2020). «Определители нормализованных верхнечешских матриц Хессенберга» . Электронный журнал линейной алгебры . 36 (36): 352–366. дои : 10.13001/ela.2020.5053 . S2CID 191136476 .
- ^ Чан, Юнис Ю.С.; Корлесс, Роберт М.; Гонсалес-Вега, Лауреано; Сендра, Дж. Рафаэль; Сендра, Хуана (май 2022 г.). «Внутренние богемные инверсии» . Прикладная математика и вычислительная техника . 421 (15): 126945. doi : 10.1016/j.amc.2022.126945 . S2CID 246318540 .
- ^ Богоя, Мануэль; Серра-Капиццано, Стефано; Тротти, Кен (2022). «Последовательности богемских матриц Верхнего Гессенберга и Теплица: примечание об их асимптотических собственных значениях и сингулярных значениях» (PDF) . Электронные труды по численному анализу . 55 : 76–91. дои : 10.1553/etna_vol55s76 . S2CID 243772914 . Архивировано (PDF) из оригинала 3 марта 2022 года . Проверено 3 марта 2022 г.
- ^ Холл, Фрэнк Дж; Ли, Чжуншань (2013). Хогбен, Лесли (ред.). Матрицы шаблонов знаков (2-е изд.). Справочник по линейной алгебре: CRC Press. стр. 42-1–42-32.