It may take some reordering of the rows (and correspondingly the columns) to make $A_1$ nonsingular.
If it is, consider $$ A $( A+I) \pmatrix{A_1^{-1} & -A_1^{-1} B\cr 0 & I\cr} = \pmatrix{I & 0\cr B^T A_1^{-1} & A_2 - B^T A_1^{-1} B\cr}$$
If this has rank $k$, the lower right block must be $0$.

