Formulas for determinant and characteristic polynomial of seven-like matrices

Authors

DOI:

https://doi.org/10.17721/1812-5409.2024/2.12

Keywords:

matrix, determinant, characteristic polynomial, renewable resources management, forest management

Abstract

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

2025-01-29

How to Cite

Fisunenko, A. (2025). Formulas for determinant and characteristic polynomial of seven-like matrices. Bulletin of Taras Shevchenko National University of Kyiv. Physical and Mathematical Sciences, 79(2), 72–79. https://doi.org/10.17721/1812-5409.2024/2.12

Issue

Section

Computer Science and Informatics