Efficiently computing the permanent and Hafnian of some banded Toeplitz matrices |
| |
Authors: | Moshe Schwartz |
| |
Institution: | Department of Electrical and Computer Engineering, Ben-Gurion University, Beer Sheva 84105, Israel |
| |
Abstract: | We present a new efficient method for computing the permanent and Hafnian of certain banded Toeplitz matrices. The method covers non-trivial cases for which previous known methods do not apply. The main idea is to use the elements of the first row and column, which determine the entire Toeplitz matrix, to construct a digraph in which certain paths correspond to permutations that the permanent and Hafnian count. Since counting paths can be done efficiently, the permanent and Hafnian for those matrices is easily obtainable. |
| |
Keywords: | 15A15 15A36 |
本文献已被 ScienceDirect 等数据库收录! |
|