AbstractFulton proves that the matrix Schubert variety $$\overline{X_{\pi }} \cong Y_{\pi } \times \mathbb {C}^q$$ X π ¯ ≅ Y π × C q can be defined via certain rank conditions encoded in the Rothe diagram of $$\pi \in S_N$$ π ∈ S N . In the case where $$Y_{\pi }:={{\,\textrm{TV}\,}}(\sigma _{\pi })$$ Y π : = TV ( σ π ) is toric (with respect to a $$(\mathbb {C}^*)^{2N-1}$$ ( C ∗ ) 2 N - 1 action), we show that it can be described as a toric (edge) ideal of a bipartite graph $$G^{\pi }$$ G π . We characterize the lower dimensional faces of the associated so-called edge cone $$\sigma _{\pi }$$ σ π explicitly in terms of subgraphs of $$G^{\pi }$$ G π and present a combinatorial study for the first-order deformations of $$Y_{\pi }$$ Y π . We prove that $$Y_{\pi }$$ Y π is rigid if and only if the three-dimensional faces of $$\sigma _{\pi }$$ σ π are all simplicial. Moreover, we reformulate this result in terms of the Rothe diagram of $$\pi $$ π .