(0,1)矩阵矩阵积和式的上下界.pdf

The upper bound and lower bound for the permanent of (0, 1)-matrices Zhang Xueyuan Zhu Xiaoying Wang Cuiqi ? (School of Science, China University of Mining and Technology, Xuzhou, Jiangsu, 221008) Abstract: Let A = [aij] be an n × n matrix with 0-1 entries. If we call a series of elements the diagonal line such that any two of them are not in the same row and are not in the same column, then the permanent of A is the number of diagonal lines whose entries are all 1s. let τ be the number of zeros in matrix A. In this paper, we obtained a new upper bound and lower bound for the permanent of (0, 1)-matrices with τ ≤ n. Key words permanent; (0, 1)-matrix; upper bound; lower bound; diagonal line 1 Introduction Let F be a subset of a number field, and let Mm,n(F ) denote the set of all m×n matrices with entries in F, and let Mn(F ) = Mn,n(F ). Note that Bn = Mn({0, 1}). A ∈ Bn , the permanent of A is defined as PerA = ∑ σ n∏ i=1 ai, σ(i) where the sum goes over every permutation σ of the set {1, 2, · · · , n}. Per A looks similar to the determinant of matrices. However, it is much harder to be computed. In fact, in 1979, Valiant [1,2] proved that determining the permanent of a (0, 1)-matrix is a NP-complete problem. Therefore, estimating the upper and lower bounds of PerA becomes important. ?Zhang Xueyuan(1978- ), female, born in Jiangsu Xuzhou, graduate student of China University of Mining and Technology, Email: zhang xue yuan@ 1 The following are the well known general lower bound and upper bound for the perma- nent of (0, 1)-matrices. Theorem 1.1(Minc, [3]) Let A ∈ Bn be fully indecomposable, then PerA ≥ ‖A‖ ? 2n + 2 where ‖A‖ = n∑ j=1 n∑ i=1 aij, (A = [aij]). Let P ∈ Bn be a permutation matrix(each row and each column have exactly one 1-entry), two matrices A and B are permutation similar if for some permutation matrix P , A = PBP?1, denoted A ～p B. A matrix A ∈ Mn is partly decomposable if A ～p A1, A1 = [ B 0 C D ] , where B and D are all square matrix. Then the