Bài 6

Cho

A=(a_{ij})

(

i,j=1,2,\ldots,n

) là ma trận vuông có các phần tử nguyên không âm. Giả sử mỗi khi

a_{ij}=0

, tổng các phần tử ở hàng

i

và cột

j

ít nhất là

n

. Chứng minh tổng tất cả phần tử của ma trận ít nhất bằng

n^2/2

Bước 1 trên 7: Tối đa hóa các số 0 trên đường chéo bằng hoán vị

Bước trước Bước tiếp

a_{11}=a_{22}=\cdots=a_{kk}=0

Phân tích chi tiết

Giả thiết và tổng toàn ma trận không đổi khi đổi chỗ hàng, cột hoặc chuyển vị. Đổi chỗ để số lớn nhất $k$ các phần tử 0 nằm trên đường chéo chính, tức $a_{11}=a_{22}=\cdots=a_{kk}=0$ . Nếu không có phần tử 0 thì tổng ít nhất là $n^2$ và ta xong.