Permanents of Hessenberg (0,1)-matrices

被引：0

作者：

Olesky, DD ^{[1
]}

Shader, B

van den Driessche, P

机构：

[1] Univ Victoria, Dept Comp Sci, Victoria, BC V8W 3P6, Canada

[2] Univ Wyoming, Dept Math, Laramie, WY 82071 USA

[3] Univ Victoria, Dept Math, Victoria, BC V8W 3P4, Canada

来源：

ELECTRONIC JOURNAL OF COMBINATORICS | 2005年 / 12卷 / 01期

关键词：

D O I：

暂无

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Let P (m;n) denote the maximum permanent of an n-by-n lower Hessenberg (0;1)-matrix with m entries equal to 1. A "staircased" structure for some matrices achieving this maximum is obtained, and recursive formulas for computing P (m;n) are given. This structure and results about permanents are used to determine the exact values of P (m;n) for n <= m <= 8n/3 and for all nnz(H-n)-nnz(H-[n/2]) <= m <= nnz(Hn), where nnz(H-n)=(n(2)=3n-2)/2 is the maximum number of ones in an n-by-n Hessenberg (0;1)-matrix.

引用

页数：25

共 5 条

[1] Brualdi R. A., 1991, COMBINATORIAL MATRIX, V39
[2] MAXIMUM PERMANENTS OF MATRICES OF ZEROS AND ONES
BRUALDI, RA
GOLDWASSER, JL
MICHAEL, TS
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES A, 1988, 47 (02) : 207 - 245
[3] An update on Minc's survey of open problems involving permanents
Cheon, GS
Wanless, IM
[J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2005, 403 : 314 - 342
[4] MINC H, 1978, ENCY MATH APPL, V6
[5] Extremes of permanents of (0,1)-matrices
Song, SZ
Hwang, SG
Rim, SH
Cheon, GS
[J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2003, 373 : 197 - 210

← 1 →