Abstract: For good security and large payload in steganography, it is desired to embed as many messages as possible per change of the cover-object, i.e., to have high embedding efficiency. Matrix embedding is the most popular method for increasing the embedding efficiency. Matrix embedding based on random linear codes, proposed by Fridrich, can achieve high embedding efficiency, but cost high computational complexity. In this paper, Fridrichs matrix embedding is improved by majority-vote parity check. First, a new cover is constructed from the original cover block with several control-bits by exclusive-or operations. Second, the matrix embedding is executed on the new cover, and a modification pattern with few changes on the original cover can be fast found by investigating the states of the control-bits. Analysis and experimental results show that the proposed method can flexibly trade embedding efficiency for embedding speed, or vice versa. Comparing with Fridrichs method, the computational complexity of the novel method exponentially decreases with increasing the number of the control-bits when embedding efficiency is unchangeable. Comparing with previous fast matrix embedding methods, the proposed method can reach higher embedding efficiency with faster embedding speed.