Matrix embedding is a previously introduced coding method that is used in steganography to improve the embedding efficiency (increase the number of bits embedded per embed- ding change). Higher embedding efficiency translates into better steganographic security. This gain is more important for long messages than for shorter ones because longer messages are in general easier to detect. In this paper, we present two new approaches to matrix embedding for large payloads suitable for practical steganographic schemes—one based on a family of codes constructed from simplex codes and the second one based on random linear codes of small dimension. The embedding efficiency of the proposed methods is evaluated with respect to theoretically achievable bounds. We describe two approaches. The first one is based on simplex codes and codes constructed from them, while the second approach uses random linear codes of small dimension. In Section II, we introduce the terminology and basic concepts of linear codes necessary to explain the embedding methods. In Section III, we briefly describe the principles of matrix embedding and state known bounds on achievable embedding efficiency. Matrix embedding based on simplex codes and random linear codes with small dimension is explained in Section IV. In the same section, the performance is compared to theoretically achievable bounds. Pseudo-codes are used to describe the embedding and extraction algorithms to ease the implementation and make this text self-contained. The paper is concluded in Section V.