New Algorithm for Determinant of Matrices Via Combinatorial Approach

New Algorithm for Determinant of Matrices Via Combinatorial Approach

Methods for finding determinants for matrices have long been explored and attracted interest of numerous researchers. However, most of the existing methods are tedious and require lengthy computation time particularly as the size of matrices becomes larger. Therefore, this study attempts to develop...

Full description

Saved in:
Bibliographic Details
Main Author: Zake, Lugen M.
Format: Thesis
Language:eng
eng
Published: 2012
Subjects:
QA299.6-433 Analysis
Online Access:https://etd.uum.edu.my/3290/1/LUGEN_M._ZAKE.pdf
https://etd.uum.edu.my/3290/4/LUGEN_M._ZAKE.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
id my-uum-etd.3290
record_format uketd_dc
institution Universiti Utara Malaysia
collection UUM ETD
language eng
eng
advisor Ibrahim, Haslinda
Omar, Zurni
topic QA299.6-433 Analysis
spellingShingle QA299.6-433 Analysis
Zake, Lugen M.
New Algorithm for Determinant of Matrices Via Combinatorial Approach
description Methods for finding determinants for matrices have long been explored and attracted interest of numerous researchers. However, most of the existing methods are tedious and require lengthy computation time particularly as the size of matrices becomes larger. Therefore, this study attempts to develop a new method which can reduce determinant computation time for matrices of any order. The developed method was based on permutations which were generated using starter sets. All starter sets for n elements were obtained by using combinatorial approach which then produced all n! distinct permutations. This starter sets strategy was proven to be more efficient if compared to other existing methods for listing all permutations such as lexicographic method. All permutations obtained were then used to construct a new method for finding determinants of n x n matrices. This study also produced a new theorem for finding determinant of n x n matrices and this theorem was proven to be equivalent to the existing theorem i.e Leibniz theorem. Besides that, several new theoretical works and mathematical properties for generating permutation and determining determinant were also constructed to verify the new developed method. The numerical results revealed that the determinant computation time for the new method was faster if compared to the existing methods. Testing of the new method on several special matrices such as Toeplitz, Hilbert and Hessenberg matrices was also carried out to prove the efficiency of the developed method. The numerical results also indicated that the new method outperformed Gauss and Gauss Jordon methods in term of computation time.
format Thesis
qualification_name Ph.D.
qualification_level Doctorate
author Zake, Lugen M.
author_facet Zake, Lugen M.
author_sort Zake, Lugen M.
title New Algorithm for Determinant of Matrices Via Combinatorial Approach
title_short New Algorithm for Determinant of Matrices Via Combinatorial Approach
title_full New Algorithm for Determinant of Matrices Via Combinatorial Approach
title_fullStr New Algorithm for Determinant of Matrices Via Combinatorial Approach
title_full_unstemmed New Algorithm for Determinant of Matrices Via Combinatorial Approach
title_sort new algorithm for determinant of matrices via combinatorial approach
granting_institution Universiti Utara Malaysia
granting_department Awang Had Salleh Graduate School of Arts & Sciences
publishDate 2012
url https://etd.uum.edu.my/3290/1/LUGEN_M._ZAKE.pdf
https://etd.uum.edu.my/3290/4/LUGEN_M._ZAKE.pdf
_version_ 1747827539197296640
spelling my-uum-etd.32902016-04-27T07:58:50Z New Algorithm for Determinant of Matrices Via Combinatorial Approach 2012 Zake, Lugen M. Ibrahim, Haslinda Omar, Zurni Awang Had Salleh Graduate School of Arts & Sciences Awang Had Salleh Graduate School of Arts and Sciences QA299.6-433 Analysis Methods for finding determinants for matrices have long been explored and attracted interest of numerous researchers. However, most of the existing methods are tedious and require lengthy computation time particularly as the size of matrices becomes larger. Therefore, this study attempts to develop a new method which can reduce determinant computation time for matrices of any order. The developed method was based on permutations which were generated using starter sets. All starter sets for n elements were obtained by using combinatorial approach which then produced all n! distinct permutations. This starter sets strategy was proven to be more efficient if compared to other existing methods for listing all permutations such as lexicographic method. All permutations obtained were then used to construct a new method for finding determinants of n x n matrices. This study also produced a new theorem for finding determinant of n x n matrices and this theorem was proven to be equivalent to the existing theorem i.e Leibniz theorem. Besides that, several new theoretical works and mathematical properties for generating permutation and determining determinant were also constructed to verify the new developed method. The numerical results revealed that the determinant computation time for the new method was faster if compared to the existing methods. Testing of the new method on several special matrices such as Toeplitz, Hilbert and Hessenberg matrices was also carried out to prove the efficiency of the developed method. The numerical results also indicated that the new method outperformed Gauss and Gauss Jordon methods in term of computation time. 2012 Thesis https://etd.uum.edu.my/3290/ https://etd.uum.edu.my/3290/1/LUGEN_M._ZAKE.pdf text eng validuser https://etd.uum.edu.my/3290/4/LUGEN_M._ZAKE.pdf text eng public Ph.D. doctoral Universiti Utara Malaysia Althoen,S.C., & McLaughlin,R. (1987). Gauss-Jordan reduction : A brief history. Journal American Mathematical Monthly, 94(2), 130-142. Bareiss,E.H. (1968). Sylvester's identity and multistep integer-preserving Gaussian elimination. Mathematics of Computation, 22(103), 565-578. Benno,F. (2008). Modified Gauss algorithm for matrices with symbolic entries. ACM Communications in Computer Algebra, 42(3), 108-121. Cinkir,Z. (2011). Computing the determinant of pent diagonal toeplitz matrices in logarithmic time. Retrieved on March 12, 2011, from: http://arxiv.org/PS_cache/arxiv/pdf /l10211102.0453v1.pdf. Choi,M.D. (1983).Tricks or treats with the Hilbert Matrix. Journal of Arts and Sciences of American Mathematical Monthly, 90, 301-312. Clarkson,K.L. (1992).Safe and effective determinant evaluation. In T.I.INC (Ed.),Proceedings of the 33rd annual symposium on, foundations of computer science (pp.387-395). Pittsburgh, PA.: IEEE. Curtis,A.R., & Reid,K.J. (1972).On the automatic scaling of matrices for Gaussian elimination. IMA Journal of Applied Mathematics, 10(1), 118-124. Dingle,B.M. (2005).Calculating determinants of symbolic and numeric matrices. Texas. Retrieved on April 16, 2011. from : http://www.cs.tamu.edu/academics/tr/tamu-cs-tr-2005-11-4. Dubbs,C., & Siege],D. (1987). Computing determinants. The College Mathematics Journal, 18, 48-50. Eberly,D. (2007). The Laplace expansion theorem: Computing the determinants and inverses of matrices. Geometric Tools, LLC. Retrieved on April 16, 2011, from:http://www.geometric- tools.com/Documentation/LaplaceExpansionTheorem. Elouafi,M., & Hadj-Aiat,D.A. (2009).A recursion formula for the characteristic polynomial of Hessenberg matrices. Applied Mathematics and Computation, 208, 177-179. Fike,C.T. (1975). A permutation generation method. The Computer Journal, 18(1), 21-22. Garloff,J.U. (2009). Interval Gaussian elimination with pivot tightening. SIAM Journal on Matrix Analysis and Application, 30, 1761-1772. Gentleman,W.M., & Johnson,S.C. (1974). The evaluation of determinants by expansion by minors and the general problem of substitution. Mathematics of Computation, 28(126), 543- 548. Goldfinger,Y. (2008). Determinant by cofactor expansion using the cell processor. CMSC 491A. Retrieved on May 13, 2011, From: http://mc2.umbc.edu/docs/goldfinger.pdf Griss,M.L. (1976). An efficient sparse minor expansion algorithm. In J.Gosden, & O.G.Johnson (Ed.), ACM National Conference 76, Proceedings of the association for computing machinery annual conference (pp.429-434). New York, NY: ACM. Hajrizaj,D. (2009).New method to compute the determinant of a 3x3 matrix. International Journal of Algebra, 3, 211-219. Horn,R.A., & Johnson,C.R. (1991).Matrix analysis.Cambridge, United Kingdom. Huang,T., & Le,J. (2008). A note on computing the inverse and the determinant of a pent diagonal Toeplitz matrix. Applied Mathematics and Computation, 206, 327-331. Ibrahim,H., Omar,Z. & Rohni,A.M. (2010). New algorithm for listing all permutations. Modern Applied Science, 4(2),89-93 Iqbal,K. (1995). An algorithm for computation of determinants of polynomial matrices, In H.Lane, M.Tomizuka, V.Cheng, & M.Peshkin (Eds.), Proceedings of the American automatic control conference on the international federation of automatic control. (pp.2536-2537). Seattle, WA, USA: IEEE. Knuth,D.E. (2005). Generating All Tuples and Permutations. The Art of Computer Programming. Addison-Wesley. (4), (pp.1- 26). Lehmer,D.H. (1960). Teaching combinatorial tricks to a computer. In X.R.Bellman, & M.Hal, Jr (Ed.), Proceedings of Svmposium Applied Mathematcs, Combinatorial Analysis. (pp. 179-193). Providence, R.I.: Amer. Math. Society. Li,Y. (2007). An effective algorithm of computing symbolic determinants with multivariate polynomial entries. Applied Mathematics and Computation, 192, 382-388, Mahajan,M., & Vinay,V. (1997). Determinant: Combinatorics, algorithms, and complexity. Chicago Journal of Theoretical Computer Science, 1997-5, 730-738. Mani, G.Iyer, (1995).Permutation generation using matrices. Retrieved on November 01, 2010, From http://www,drdobbs.com/184409671, Press,W.H. (1986). Numerical Recipes . Cambridge, United States of America. Rezaifar,O., & Rezaee,M. (2007). A new approach for finding the determinant of matrices. Applied Mathematics and Computation, 188, 1445-1454. Robert,K.B., Gustavson,F.G., & Willoughby,R.A. (1970).Some results on sparse matrices. Mathematics of Computation, 24, 937-954. Rohl,J.S. (1978). Generating permutations by choosing. The Computer Journal, 21(4), 302-305. Rote,G.U. (2001). Division-free algorithms for the determinant and the Pfaffian: Algebraic and combinatorial approaches. Computational Discrete Mathematics, 2122,119-135 Sasaki,T., & Murao,H. (1982).Efficient Gaussian elimination method for symbolic determinants and linear systems. ACM Transactions on Mathematical Software (TOMS), 8(3), 277-289. Sasaki,T., & Kako,F. (2007). Computing floating-point grobner bases stably. In S.M.Watt, & J.Verschelde (Ed.), Proceedings of the international workshop and International Symposium on Symbolic and Algebraic Computation,ISSAC '07 (pp.180-189). Waterloo, Canada: ACM. Sedgewick,R. (1977). Permutation generation methods. Journal Computer Science of Applied Mathematics, 9, 137-164. Sogabe,T. (2007). On a two-term recurrence for the determinant of a general matrix. Applied Mathematics and Computation, 187, 785-788. Sogabe,T. (2008a). A fast numerical algorithm for the determinant of a pent diagonal matrix. Applied Mathematics and Computation, 196, 835-841, Sogabe,T. (2008b). A note on "A fast numerical algorithm for the determinant of a pent diagonal matrix". Applied Mathematics and Computation, 201, 561-564. Sheldon,A. (1995). Down With Determinants. Mathematical Association of America. 102, 139-154. Thongchiew,K. (2007). A computerized algorithm for generating permutation and its application in determining a determinant. World Academy of Science, Engineering and Technology, 27, 178-183. Vein,R., & Dale,P. (1998). Determinants and Their Applications in Mathematical Physics. Springer-Verlag New York.

Similar Items