Matrix embedding is proved an effective way to improve embedding efficiency of steganography, and usually, higher dimensional matrix will provide better embedding efficiency. However, the sender might suffer huge computational complexity when employing high dimensional matrix. In this paper, a variation of matrix embedding is proposed. Instead of finding a coset leader as the modification of the cover image (which is the most time consuming step in matrix embedding), we turn to finding a vector in the coset which has relatively small Hamming weight. Such a vector can be found at reduced computational cost. Consequently, higher dimensional matrix can be used for practically implementable matrix embedding. The parity check matrix of random linear code is used in the experiments. It has shown that the proposed scheme can enhance the practicability and efficiency of the conventional matrix embedding.