Matrix mortality problem: Difference between revisions

Revision as of 23:46, 25 April 2024

Latest revision as of 01:44, 11 June 2025

(5 intermediate revisions by 2 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>

Line 45 ⟶ 119:

| volume = 35

| date = 2002

| issue = 4
| pages = 433–448

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

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

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}}