How would changing of elements of matrix(from zeros to non-zeros) affect its rank.

For a block diagonal matrix of the form $\left[\begin{array}{ccc}A_1 & & O\\ & \ddots & \\ O & & A_L\end{array}\right]$, where $A_1,\ldots,A_L$ are matrices of size $K\times K$, the rank of it is $R\leq KL$. My question is, if I randomly pick up one zero from the off-block-diagonal part and change that to a non-zero element, how would that affect the rank of this matrix (decrease, increase, non-increase, non-decrease, equal)? Intuitively it looks like non-decreasing, but how to give a mathematical proof on that? Thanks.

-
$\operatorname{rank}(A+B) \le \operatorname{rank}(A) + \operatorname{rank}(B)$ –  user2468 Mar 7 '12 at 2:00

The rank is the number of linearly independant columns (or rows). Changing a single entry outside of the block diagonal cannot decrease the rank, since that column will now clearly be linearly independant from the other columns whose nonzero part are in the same block. (This could create new dependence relations with columns whose nonzero parts are in other blocks, but only if this column were 0 to begin with.) So the rank will go up or stay the same.

If you change multiple entries off the block diagonal, and change entries that are not in the same $K \times K$ block, all bets are off.

-