Formulas for determinant and characteristic polynomial of seven-like matrices
DOI:
https://doi.org/10.17721/1812-5409.2024/2.12Keywords:
matrix, determinant, characteristic polynomial, renewable resources management, forest managementAbstract
Finding the determinant and characteristic polynomial is the classic problem of linear algebra that arises in some applications utilizing matrices. There exist formulas and algorithms for calculating the determinant and characteristic polynomial of matrices with general structure, however, in some cases, a matrix has a special structure that lets the determinant and/or characteristic polynomial be calculated more efficiently. E.g., the determinant of upper and lower triangular matrices can be calculated as a product of their diagonal entries in time, linear in terms of the matrix’s size.
In this paper, we derived the formulas and algorithms for determinant or determinant and characteristic polynomial of what we called seven-like matrices, which include the matrix introduced in M. B. Usher’s renewable resources management model, by utilizing the properties of determinants and characteristic polynomials, and the seven-like matrices’ special structure.
We implemented our algorithms in Python 3.10.4 and tested their correctness on different values of matrix’s size and its elements. In all these experiments, the results matched the reference values, some up to a negligibly small relative error due to the floating-point arithmetic.
The proposed algorithms have linear computational time complexity, therefore, for seven-like matrices, they are more asymptotically time-efficient than the most asymptotically time-efficient currently known algorithms for finding the determinant and characteristic polynomial, respectively, of the matrices with general structure, and thus our algorithms can be utilized in the applications with seven-like matrices (including applications of Usher’s model). Runtime measurements can be conducted in our further research to practically verify these asymptotics.
Pages of the article in the issue: 72 - 79
Language of the article: English
References
Alman, J., Duan, R., Williams, V. V., Xu, Y., Xu, Z., & Zhou, R. (2024). More Asymmetry Yields Faster Matrix Multiplication. arXiv preprint.
arXiv, 2404, 16349.
Chiantini, L., Hauenstein, J. D., Ikenmeyer, C., Landsberg, J. M., & Ottaviani, G. (2018). Polynomials and the exponent of matrix multiplication. Bulletin of the London Mathematical Society, 50(3), 369–389.
Dumas, J. G., Pernet, C., & Wan, Z. (2005, July). Efficient computation of the characteristic polynomial. In Proceedings of the 2005
international symposium on Symbolic and algebraic computation, 140–147.
Fawzi, A., Balog, M., Huang, A. et al. (2022). Discovering faster matrix multiplication algorithms with reinforcement learning. Nature, 610, 47–53. https://doi.org/10.1038/s41586-022-05172-4
Fisunenko, A. (2024, November 8). The experiments conducted to verify the correctness of algorithms for seven-like matrices on certain data. GitHub. https://github.com/artandfi/seven-like-matrices
Harris, C. R., Millman, K. J., van der Walt, S. J. et al. (2020). Array programming with NumPy. Nature, 585, 357–362. https://doi.org/10.1038/s41586-020-2649-2.
Keller-Gehrig, W. (1985). Fast algorithms for the characteristics polynomial. Theoretical computer science, 36, 309–317.
Leslie, P. H. (1945). On the use of matrices in certain population mathematics. Biometrika, 33(3), 183–212.
Meurer, A., Smith, C. P., Paprocki, M. et al. (2017). SymPy: symbolic computing in Python. PeerJ Computer Science, 3, e103.
https://doi.org/10.7717/peerj-cs.103
Usher, M. B. (1966). A matrix approach to the management of renewable resources, with special reference to selection forests. Journal of Applied Ecology, 355–367.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Artem Fisunenko

This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).