ポイントは二重和を交換するだけですね.
A := (a[i, j]), B := (b[i, j]), C := AB =: (c[i, j]) とすると
c[i, j] = Σ_k a[i, k]b[k, j]
です.なのでこれが非負であることは明らかです.また和の交換をすれば列の和が1になることもカンタンに示せます.
Σ_j c[i, j] = Σ_j Σ_k a[i, k]b[k, j] = Σ_k Σ_j a[i, k]b[k, j]
= Σ_k a[i, k] Σ_j b[k, j] = Σ_k a[i, k] = 1.