- This paper focuses on the Gaussian two-terminal source coding problem under a covariance matrix distortion constraint, which subsumes the quadratic Gaussian two-terminal source coding problem with individual distortion constraints, whose complete solution is known. Different from existing schemes which are either random or structured, we propose a new hybrid random-structured scheme with a sum-rate strictly smaller than the quantize-and-bin (QB) upper bound in certain cases. The first layer of our scheme is a QB random coding scheme attempting to achieve an intermediate distortion matrix that is as symmetric as possible. The second layer is a structured scheme that targets at reconstructing a weighted difference of the observed sources conditioned on their quantized versions in the first layer. We prove that the gap between the sum-rate of our scheme and its lower bound is no larger than two bits per sample, in particular, this gap decreases to exactly one bit per sample when the source covariance matrix is symmetrifiable in the sense that the intermediate covariance matrix can be made purely symmetric. 2012 IEEE.