License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.10
URN: urn:nbn:de:0030-drops-126807
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12680/
Arvind, V. ;
Chatterjee, Abhranil ;
Datta, Rajit ;
Mukhopadhyay, Partha
A Special Case of Rational Identity Testing and the Brešar-Klep Theorem
Abstract
We explore a special case of rational identity testing and algorithmic versions of two theorems on noncommutative polynomials, namely, Amitsur's theorem [S.A Amitsur, 1966] and the Brešar-Klep theorem [Brešar and Klep, 2008] when the input polynomial is given by an algebraic branching program (ABP). Let f be a degree-d n-variate noncommutative polynomial in the free ring Q<x_1,x_2,...,x_n> over rationals.
1) We consider the following special case of rational identity testing: Given a noncommutative ABP as white-box, whose edge labels are linear forms or inverses of linear forms, we show a deterministic polynomial-time algorithm to decide if the rational function computed by it is equivalent to zero in the free skew field Q<(X)>. Given black-box access to the ABP, we give a deterministic quasi-polynomial time algorithm for this problem.
2) Amitsur's theorem implies that if a noncommutative polynomial f is nonzero on k x k matrices then, in fact, f(M_1,M_2,...,M_n) is invertible for some matrix tuple (M_1,M_2,...,M_n) in (M_k(ℚ))^n. While a randomized polynomial time algorithm to find such (M_1,M_2,...,M_n) given black-box access to f is simple, we obtain a deterministic s^{O(log d)} time algorithm for the problem with black-box access to f, where s is the minimum ABP size for f and d is the degree of f.
3) The Brešar-Klep Theorem states that the span of the range of any noncommutative polynomial f on k x k matrices over Q is one of the following: zero, scalar multiples of I_k, trace-zero matrices in M_k(Q), or all of M_k(Q). We obtain a deterministic polynomial-time algorithm to decide which case occurs, given white-box access to an ABP for f. We also give a deterministic s^{O(log d)} time algorithm given black-box access to an ABP of size s for f. Our algorithms work when k >= d.
Our techniques are based on some automata theory combined with known techniques for noncommutative ABP identity testing [Ran Raz and Amir Shpilka, 2005; Michael A. Forbes and Amir Shpilka, 2013].
BibTeX - Entry
@InProceedings{arvind_et_al:LIPIcs:2020:12680,
author = {V. Arvind and Abhranil Chatterjee and Rajit Datta and Partha Mukhopadhyay},
title = {{A Special Case of Rational Identity Testing and the Bre{\v{s}}ar-Klep Theorem}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {10:1--10:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-159-7},
ISSN = {1868-8969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12680},
URN = {urn:nbn:de:0030-drops-126807},
doi = {10.4230/LIPIcs.MFCS.2020.10},
annote = {Keywords: Rational identity testing, ABP with inverses, Bre{\v{s}}ar-Klep Theorem, Invertible image, Amitsur’s theorem}
}
|
Keywords: |
|
Rational identity testing, ABP with inverses, Brešar-Klep Theorem, Invertible image, Amitsur’s theorem |
|
Collection: |
|
45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
18.08.2020 |
