Проблема смертности матрицы
В информатике проблема матричной смертности (или проблема смертной матрицы ) — это проблема решения , которая спрашивает, учитывая конечный набор матриц размера n × n с целыми коэффициентами, может ли нулевая матрица быть выражена как конечное произведение матриц из этого набора. .
Известно, что матричная проблема смертности неразрешима при n ≥ 3. [ 1 ] . Фактически, это уже неразрешимо для наборов из 6 матриц (или более), когда n = 3, для 4 матриц, когда n = 5, для 3 матриц, когда n = 9, и для 2 матриц, когда n = 15 [ 2 ] .
В случае n = 2 вопрос о разрешимости матричной смертности остается открытым, но решено несколько частных случаев: проблема разрешима для наборов из двух матриц. [ 3 ] , а для наборов матриц, содержащих не более одной обратимой матрицы [ 4 ] .
Примечания
[ редактировать ]- ^ Патерсон, Майкл С. (1970). «Неразрешимость в матрицах 3 × 3 ». Исследования по прикладной математике . 49 : 105–107. дои : 10.1002/sapm1970491105 . МР 0255400 .
- ^ Кассень, Жюльен; Халава, Веса; Харью, Терм; Николас, Франсуа (2014). «Более жесткие границы неразрешимости для матричной смертности, проблем с нулем в углу и многого другого». arXiv : 1404.0644 [ cs.DM ].
- ^ Бурне, Оливье; Браницки, Майкл (2002). «Проблема смертности для матриц малых размерностей» (PDF) . Теория вычислительных систем . 35 : 433–448. дои : 10.1007/s00224-002-1010-5 .
- ^ Хекман, Кристофер Карл (2019). «Матричная проблема смертности 2 × 2 и обратимые матрицы». arXiv : 1912.09991 [ math.RA ].
 | Эта по информатике статья незавершена . Вы можете помочь Википедии, расширив ее . |