Symbolic matrices in non-commuting variables, and the related structural and algorithmic questions, have a remarkable number of diverse origins and motivations. They arise independently in (commutative) invariant theory and representation theory, linear algebra, optimization, linear system theory, quantum information theory, and naturally in non-commutative algebra. In this paper we present a deterministic polynomial time algorithm for testing if a symbolic matrix in non-commuting variables over Q is invertible or not. The analogous question for commuting variables is the celebrated polynomial identity testing (PIT) for symbolic determinants. In contrast to the commutative case, which has an efficient probabilistic algorithm, the best previous algorithm for the non-commutative setting required exponential time [1] (whether or not randomization is allowed). The main (simple!) technical contribution of this paper is an analysis of an existing "operator scaling" algorithm due to Gurvits [2], which solved some special cases of the same problem we do (these already include optimization problems like matroid intersection). This analysis of the running time of Gurvits' algorithm combines results from some of these different fields. It lower bounds a parameter of quantum maps called capacity, via degree bounds from algebraic geometry on the Left- Right group action, which in turn is relevant due to certain characterization of the free skew (non-commutative) field. Via the known connections above, our algorithm efficiently solves several problems in different areas which had only exponential-time algorithms prior to this work. These include the "word problem" for the free skew field (namely identity testing for rational expressions over non-commuting variables), testing if a quantum operator is "rank decreasing", and the membership problem in the null-cone of a natural group action arising in Geometric Complexity Theory (GCT). Moreover, extending our algorithm to actually compute the non-commutative rank of a symbolic matrix, yields an efficient factor-2 approximation to the standard commutative rank. This naturally suggests the challenge to improve this approximation factor, noting that a fullypolynomial approximation scheme may lead to a deterministic PIT algorithm. Finally, our algorithm may also be viewed as efficiently solving a family of structured systems of quadratic equations, which seem general enough to encode interesting decision and optimization problems 1.@en

The presence of a wide range of high- and low-resolution devices renders the images to experience changes in respect to aspect ratio and size for better adaptability. This paper proposes a novel and effective technique that vanquishes the problems encountered in the conventional seam carving method. To achieve minimum distortion in salient objects of the image, the proposed technique restricts intersection or overlapping of multiple seams in the horizontal and vertical direction and bypasses them to the neighboring low energy pixel. The proposed technique hinders the pixel selection from a single row or column beyond the defined threshold so as to save the image information and reduce distortion at a single location. To justify the effectiveness of the proposed technique, results have been presented in comparison with the five state-of-the-art image retargeting techniques. Compared with the conventional techniques, this technique shows remarkable results in terms of low distortion percentage. The proposed technique also produces excellent results for shrinkage and enlargement of a single image multiple times.@en