Arvind, V. ;
Chatterjee, Abhranil ;
Datta, Rajit ;
Mukhopadhyay, Partha
A Special Case of Rational Identity Testing and the BrešarKlep 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šarKlep theorem [Brešar and Klep, 2008] when the input polynomial is given by an algebraic branching program (ABP). Let f be a degreed nvariate 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 whitebox, whose edge labels are linear forms or inverses of linear forms, we show a deterministic polynomialtime algorithm to decide if the rational function computed by it is equivalent to zero in the free skew field Q<(X)>. Given blackbox access to the ABP, we give a deterministic quasipolynomial 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 blackbox access to f is simple, we obtain a deterministic s^{O(log d)} time algorithm for the problem with blackbox access to f, where s is the minimum ABP size for f and d is the degree of f.
3) The BrešarKlep 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, tracezero matrices in M_k(Q), or all of M_k(Q). We obtain a deterministic polynomialtime algorithm to decide which case occurs, given whitebox access to an ABP for f. We also give a deterministic s^{O(log d)} time algorithm given blackbox 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}}arKlep Theorem}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {10:110:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771597},
ISSN = {18688969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12680},
URN = {urn:nbn:de:0030drops126807},
doi = {10.4230/LIPIcs.MFCS.2020.10},
annote = {Keywords: Rational identity testing, ABP with inverses, Bre{\v{s}}arKlep Theorem, Invertible image, Amitsur’s theorem}
}
18.08.2020
Keywords: 

Rational identity testing, ABP with inverses, BrešarKlep Theorem, Invertible image, Amitsur’s theorem 
Seminar: 

45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Issue date: 

2020 
Date of publication: 

18.08.2020 