Matrix mortality problem: Difference between revisions

Revision as of 08:08, 25 April 2024

Latest revision as of 01:44, 11 June 2025

(7 intermediate revisions by 4 users not shown)

Line 1:

In [[computer science]], the '''matrix mortality problem''' (or '''mortal matrix problem''') is a [[decision problem]] that asks, given a finite set of size ''m'' of ''n''×''n'' matrices with integer coefficients, whether the [[zero matrix]] can be expressed as a finite product of matrices from this set.

The matrix mortality problem is known to be [[undecidable problem|undecidable]] when ''n'' ≥ 3{{r|paterson}}. In fact, it is already undecidable for sets of 6

Line 5:

In the case ''n'' = 2, it is an open problem whether matrix mortality is decidable, but several special cases have been solved: the problem is decidable for sets of 2 matrices{{r|bournez-branicky}}, and for sets of matrices which contain at most one invertible matrix{{r|heckman}}.

{| class="wikitable"

|+The current frontier of knowledge

!''n''\''m''

!1

!2

!3

!4

!5

!6

|-

|2

|✅

|✅

|

|

|

|

|-

|3

|✅

|

|

|

|

|✖️

|-

|4

|✅

|

|

|

|

|✖️

|-

|5

|✅

|

|

|✖️

|✖️

|✖️

|-

|...

|✅

|

|

|✖️

|✖️

|✖️

|-

|9

|✅

|

|✖️

|✖️

|✖️

|✖️

|-

|...

|✅

|

|✖️

|✖️

|✖️

|✖️

|-

|15

|✅

|✖️

|✖️

|✖️

|✖️

|✖️

|}

==NotesReferences==

<references>

<ref name=paterson>{{cite journal

| last = Paterson | first = Michael S. | author-link = Mike Paterson

{{ cite journal

| doi = 10.1002/sapm1970491105

| last = Paterson

| journal = Studies in Applied Mathematics

| first = Mike

| datemr = 1970255400

| pages = 105–107

| title = Unsolvability in 3×3{{math|3 &times; 3}} matrices

| journal = Studies in Applied Mathematics

| volume = 49

| year = 1970}}

| pages = 105–107

}}

</ref>

<ref name=cassaigne-halava-harju-nicolas>

Line 45 ⟶ 118:

| journal = Theory of Computing Systems

| volume = 35

| pagesdate = 433–4482002

| lastissue = Paterson4

| pages = 433–448

| doi = 10.1007/s00224-002-1010-5

| url = https://www.lix.polytechnique.fr/~bournez/load/Papier-TOCS-2002.pdf

Line 55 ⟶ 130:

| last = Heckman

| first = Christopher Carl

| title = The 2×2 Matrix Mortality Problem and Invertible MatrixMatrices

| class = math.RA

| year = 2019

Line 62 ⟶ 137:

</references>

* {{Cite journal |last1=Bell |first1=Paul |last2=Potapov |first2=Igor |date=2008-02-04 |title=On undecidability bounds for matrix decision problems |url=https://www.sciencedirect.com/science/article/pii/S0304397507007840 |journal=Theoretical Computer Science |series=Combinatorics, Automata and Number Theory |volume=391 |issue=1 |pages=3–13 |doi=10.1016/j.tcs.2007.10.025 |issn=0304-3975}}

* {{Cite report |url=https://dl.acm.org/doi/10.5555/893250 |title=Decidable and Undecidable Problems in Matrix Theory |last=Halava |first=Vesa |date=August 1997 |publisher=Turku Centre for Computer Science }}>

{{comp-sci-stub}}

[[Category:Undecidable problems]]

Line 70 ⟶ 144:

[[Category:Unsolved problems in mathematics]]

[[Category:Matrix theory]]

{{comp-sci-stub}}