A General Method for Generating Discrete Orthogonal Matrices

Discrete orthogonal matrices have applications in information coding and cryptography. It is often challenging to generate discrete orthogonal matrices. A common approach widely in use is to discretize continuous orthogonal functions that have been discovered. The need of such continuous functions is restrictive. Polynomials, as the simplest class of continuous functions, are widely studied for their orthogonality, to serve the purpose of generating orthogonal matrices. However, beginning with continuous orthogonal polynomials still takes much work. To overcome this complexity while improving the efficiency and flexibility, we present a general method for generating orthogonal matrices directly through the construction of certain even and odd polynomials from a set of distinct positive values, bypassing the need of continuous orthogonal functions. We present a constructive proof by induction that not only asserts the existence of such polynomials, but also tells how to iteratively construct them. Besides the derivation of the method as simple as a few nested loops, we discuss two well-known discrete transforms, the Discrete Cosine Transform and the Discrete Tchebichef Transform, about how they can be achieved using our method with the specific values, and how to embed them into the transform module of video coding. By the same token, we also give the examples for generating new orthogonal matrices from arbitrarily chosen values. The demonstrative experiments indicate that our method is not only simpler to implement, but also more efficient and flexible. It can generate orthogonal matrices of larger sizes, compared with those existing methods.