A Time-Reducible Approach to Compute Determinant |I-X|

Authors: Wang Xingbo

Abstract:

Computation of determinant in the form |I-X| is primary and fundamental because it can help to compute many other determinants. This article puts forward a time-reducible approach to compute determinant |I-X|. The approach is derived from the Newton’s identity and its time complexity is no more than that to compute the eigenvalues of the square matrix X. Mathematical deductions and numerical example are presented in detail for the approach. By comparison with classical approaches the new approach is proved to be superior to the classical ones and it can naturally reduce the computational time with the improvement of efficiency to compute eigenvalues of the square matrix.

Keywords: Algorithm, determinant, computation, eigenvalue, time complexity.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1125609

References:

[1] Ershaidat, M, N. History of Matrices and Determinants, Yarmouk University, Irbid Jordan, 2007, 1-6.
[2] Gunter Rote. Division-Free Algorithms for the Determinant and the Pfaffian: Algebraic and Combinatorial Approaches, Computational Discrete Mathematics, LNCS 2122, pp. 119–135, 2001.
[3] Seifullin T R. Acceleration of Computation of determinants and Characteristic polynomials without Divisions, Cybernetics and Systems Analysis, Vol. 39, No. 6, 2003.
[4] Kaltofen E. On Computing Determinants of Matrices without Divisions. Proceedings of the 1992 International Symposium on Symbolic Algebraic Computing, 1992:342-349.
[5] Villard G. Computation of the Inverse and Determinant of a Matrix (J), INRIA, (2003), pp. 29–32.
[6] Ioannis Z. Emirisa, and Victor Y. Panb, Improved Algorithms for computing determinants and resultants. Journal of Complexity 21 (2005) 43–71.
[7] Klaus Kirsten. Computation of determinants using contour integrals, American Journal of Physics.76:60-64,2008.
[8] Keček, Damira. Methods of computing determinants of the n-th order, Osječki matematički list, Vol.10 No.1 October 2010. 31–42.
[9] T Ogita. Robust Computation of Determinant (C). American Institute of Physics Conference Series, 2012, 1504(10):1119-1123.
[10] Almalki S, Alzahrani S. A Alabdullatif. New parallel algorithms for finding determinants of N×N matrices, World Congress on Computer & Information Technology, 2013:1-6.
[11] Beliakov G, Matiyasevich Y.A Parallel Algorithm for Calculation of Large Determinants with High Accuracy for GPUs and MPI clusters, arXiv:1308.1536v2,2013(8).
[12] Salman H. Abbas. Computing the Determinants in the Multiprocessor Computer. International Journal of Innovative Research in Science, Engineering and Technology, Vol. 3, Issue 8, August 2014.
[13] G Beliakov, Y Matiyasevich. A parallel algorithm for calculation of determinants and minors using arbitrary precision arithmetic. Bit Numerical Mathematics, 2015:1-18.
[14] Jia L, Yao GT. On computation determinant of circulant matrices and its application (J), Journal of Xinyang Teachers College, 2014, 18(2):131-132.
[15] Elouafi M., Dah Ahmed. A New Algorithm for the Determinant and the Inverse of Banded Matrices (J).Open Access Library Journal, 2014, 01:1-5.
[16] Awol Assen, Venkateswara Rao J.A Study on the Computation of the Determinants of a 3x3 Matrix, International Journal of Science and Research, 2014,3(6):912-921.
[17] Wang Xingbo, Xian Yaoqi. How Difficult to Compute Coefficients of Characteristic Polynomial? International Journal of Scientific and Innovative Mathematical Research (IJSIMR), 2016,3(1):7-12.
[18] K Singh.Linear algebra step by Step, Oxford Press, 2013,pp517.
[19] C D Meyer. Matrix Analysis and Applied Linear Algebra, SIAM, Philadelphia, 2000,pp489-660.
[20] G W Stewart, Matrix Algorithms, SIAM, 1998,pp176-177.
[21] S S. Skiena, The Algorithm Design Manual, Springer- Verlag London Limited, 2008, pp404-406.