Proving rank deficiency of a matrix whose elements are given by trigonometric functions

Question

I want to show that a specific $(N^2+1)\times 3N$ matrix ($N\geq 3$) is rank deficient, specifically that it has rank $3N-1$. Ideally, I would like to show that this is the case for all $N\geq 3$ but I'm also very happy if I can show the case $N=3$. Below is the matrix for $N=3$. Each element is either $0$, $1$ or a trigonometric function in two out of $2N+1$ variables ($x_i, y_i, z$; these can be chosen at random with $z\neq 2\pi m$ for $m\in\mathbb{Z}$). A formal definition of the matrix is given below. In addition, I provide the Python code which generates this matrix; this code also verifies the rank deficiency numerically.

I would like to know if there exist any techniques for showing rank deficiency which I could use to approach this problem. This is what I tried so far:

• I removed any factors that are constants per column in order to arrive at a simpler version of the column space; the matrix below is the most simple version I could come up with after removing a bunch of such factors.
• I asked Mathematica to compute the rank of the $N=3$ matrix, however, it returned $9$ as an answer, so most likely it failed the constant problem. I also asked Mathematica to compute the singular values (so I could check them myself) but it didn't finish the computation within a reasonable amount of time.
• I asked SymPy to compute the rank, the singular values, the QR decomposition and the nullspace of the $N=3$ matrix but it didn't finish the computation within a reasonable amount of time for either task.
• For $N=3$, the reduced matrix by removing the first row must have rank no larger than the original matrix. Since this reduced matrix happens to be a square matrix, I can compute the determinant. After doing trigonometric expansion of all the involved terms, the problem of the determinant being zero should be decidable (albeit computationally expensive). However, then it remains to show that the first row $[0,0,0,0,0,0,1,1,1]$ can be constructed from a linear combination of all the remaining rows. This amounts to solving $cM = \mathrm{row}_1$ which again might be too difficult to compute (as it involves division by $\sin,\cos$ terms).
• When looking at the $N^2\times N$ matrix that consists of all the column factors stacked row-wise, there are always exactly $3N-2$ non-duplicated rows in that matrix (see below for $N=3$ and $N=4$ examples). In fact, for each specific combination of all three factors $\{-1,0,1\}$, there are always two such rows in this factor matrix. Each other combination of only two factors occurs only once. So I thought about using the $3N-2$ row vectors from the actual matrix that correspond to the non-duplicated rows in the factor matrix, together with the $[0,0,0,0,0,0,1,1,1]$ row vector and show that all other row vectors can be constructed from linear combinations of these, but I couldn't come up with a solution (the problem is that every row in the actual matrix contains a different combination of $x_i,y_j$).
• I tried to find the coefficients of the nullspace "by hand" (or, rather, by being creative), however, I couldn't come up with a solution. The Harmonic Addition Theorem seemed promising and it helped me to get an expression for the sum of trigonometric terms per row, however, I couldn't figure out how to show that these expressions can be made zero for all of the rows by an appropriate choice for the linear coefficients (as these coefficients are contained inside the $\tan(\delta) = \dots$ expressions).

And that's all the techniques/approaches that I am aware of. Thus, I would be glad if someone could point me in the right direction for approaching this problem.

Formal definition of the matrix

Let $x_i,y_i,z \in \mathbb{R}$ with $0\leq i < N$ and $z \neq 2\pi m$ ($m\in\mathbb{Z}$) and $N\geq 3$.

Let $F_{kl}$ be a matrix of shape $N^2\times N$. Assume the row ordering given by $k = iN+j$ (where $i,j$ refer to the symbols $x,y$). Then $F_{kl}$ is defined in the following way:

$$ F_{kl} = \begin{cases} -1 & \; , \quad 0 &\leq l < \min(i,j+1) \\ 0 & \; , \quad \min(i,j+1) &\leq l < \max(i,j+1) \\ +1 & \; , \quad \max(i,j+1) &\leq l < N \\ \end{cases} $$

Further let $M_{kl}^{(1)}, M_{kl}^{(2)}, M_{kl}^{(3)}$ be matrices of shape $N^2\times N$; again $k = iN+j$.

$$ \begin{aligned} M_{kl}^{(1)} &= \cos\left(x_i + y_j + F_{kl}z\right)\\ M_{kl}^{(2)} &= \sin\left(x_i + y_j + F_{kl}z\right)\\ M_{kl}^{(3)} &= \left(1-|F_{kl}|\right)\cdot \begin{cases} \sin\left(x_i - y_j + \frac{z}{2}\right) & \; , \quad i \leq j\\ \sin\left(y_j - x_i + \frac{z}{2}\right) & \; , \quad i > j\\ \end{cases}\\ \end{aligned} $$

Then the matrix $M$ of interest is given by a column stack of the individual matrices $M_{kl}^{(1)},M_{kl}^{(2)},M_{kl}^{(3)}$, augmented by an additional row $[0,\dots,0,0\dots,0,1\dots,1]$:

$$ M = \begin{bmatrix} & & & & & & & & \\ & M^{(1)} & & & M^{(2)} & & & M^{(3)} & \\ & & & & & & & & \\ 0 & \dots & 0 & 0 & \dots & 0 & 1 & \dots & 1 \\ \end{bmatrix} $$

Objectives

• Conjecture 1: $M$ is rank deficient.
• Conjecture 2: $M$ has rank $3N-1$.

I am mainly interested in conjecture 1.

The matrix for $N=3$

$$ \left[\begin{matrix}0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1\\\cos{\left(x_{0} + y_{0} \right)} & \cos{\left(x_{0} + y_{0} + z \right)} & \cos{\left(x_{0} + y_{0} + z \right)} & \sin{\left(x_{0} + y_{0} \right)} & \sin{\left(x_{0} + y_{0} + z \right)} & \sin{\left(x_{0} + y_{0} + z \right)} & \sin{\left(x_{0} - y_{0} + \frac{z}{2} \right)} & 0 & 0\\\cos{\left(x_{0} + y_{1} \right)} & \cos{\left(x_{0} + y_{1} \right)} & \cos{\left(x_{0} + y_{1} + z \right)} & \sin{\left(x_{0} + y_{1} \right)} & \sin{\left(x_{0} + y_{1} \right)} & \sin{\left(x_{0} + y_{1} + z \right)} & \sin{\left(x_{0} - y_{1} + \frac{z}{2} \right)} & \sin{\left(x_{0} - y_{1} + \frac{z}{2} \right)} & 0\\\cos{\left(x_{0} + y_{2} \right)} & \cos{\left(x_{0} + y_{2} \right)} & \cos{\left(x_{0} + y_{2} \right)} & \sin{\left(x_{0} + y_{2} \right)} & \sin{\left(x_{0} + y_{2} \right)} & \sin{\left(x_{0} + y_{2} \right)} & \sin{\left(x_{0} - y_{2} + \frac{z}{2} \right)} & \sin{\left(x_{0} - y_{2} + \frac{z}{2} \right)} & \sin{\left(x_{0} - y_{2} + \frac{z}{2} \right)}\\\cos{\left(x_{1} + y_{0} - z \right)} & \cos{\left(x_{1} + y_{0} + z \right)} & \cos{\left(x_{1} + y_{0} + z \right)} & \sin{\left(x_{1} + y_{0} - z \right)} & \sin{\left(x_{1} + y_{0} + z \right)} & \sin{\left(x_{1} + y_{0} + z \right)} & 0 & 0 & 0\\\cos{\left(x_{2} + y_{0} - z \right)} & \cos{\left(x_{2} + y_{0} \right)} & \cos{\left(x_{2} + y_{0} + z \right)} & \sin{\left(x_{2} + y_{0} - z \right)} & \sin{\left(x_{2} + y_{0} \right)} & \sin{\left(x_{2} + y_{0} + z \right)} & 0 & \sin{\left(- x_{2} + y_{0} + \frac{z}{2} \right)} & 0\\\cos{\left(x_{1} + y_{1} - z \right)} & \cos{\left(x_{1} + y_{1} \right)} & \cos{\left(x_{1} + y_{1} + z \right)} & \sin{\left(x_{1} + y_{1} - z \right)} & \sin{\left(x_{1} + y_{1} \right)} & \sin{\left(x_{1} + y_{1} + z \right)} & 0 & \sin{\left(x_{1} - y_{1} + \frac{z}{2} \right)} & 0\\\cos{\left(x_{1} + y_{2} - z \right)} & \cos{\left(x_{1} + y_{2} \right)} & \cos{\left(x_{1} + y_{2} \right)} & \sin{\left(x_{1} + y_{2} - z \right)} & \sin{\left(x_{1} + y_{2} \right)} & \sin{\left(x_{1} + y_{2} \right)} & 0 & \sin{\left(x_{1} - y_{2} + \frac{z}{2} \right)} & \sin{\left(x_{1} - y_{2} + \frac{z}{2} \right)}\\\cos{\left(x_{2} + y_{1} - z \right)} & \cos{\left(x_{2} + y_{1} - z \right)} & \cos{\left(x_{2} + y_{1} + z \right)} & \sin{\left(x_{2} + y_{1} - z \right)} & \sin{\left(x_{2} + y_{1} - z \right)} & \sin{\left(x_{2} + y_{1} + z \right)} & 0 & 0 & 0\\\cos{\left(x_{2} + y_{2} - z \right)} & \cos{\left(x_{2} + y_{2} - z \right)} & \cos{\left(x_{2} + y_{2} \right)} & \sin{\left(x_{2} + y_{2} - z \right)} & \sin{\left(x_{2} + y_{2} - z \right)} & \sin{\left(x_{2} + y_{2} \right)} & 0 & 0 & \sin{\left(x_{2} - y_{2} + \frac{z}{2} \right)}\end{matrix}\right] $$

The Python code for generating the matrix and for verifying the rank deficiency numerically:

from argparse import ArgumentParser

from sympy import cos, sin, symbols, Matrix, latex


parser = ArgumentParser()
parser.add_argument('N', type=int, default=3, help='Matrix will be of shape (N^2+1, 3N)')
N = parser.parse_args().N


x = symbols([f'x{i}' for i in range(N)], real=True)
y = symbols([f'y{i}' for i in range(N)], real=True)
z = symbols('z', real=True)


def column_factors():
    """For each row of the matrix, yield the two relevant variables (v1, v2)
       as well as a list of N factors which are applied to N sets of 3 columns (type 1,2,3)."""
    for i in range(N):
        yield from ((x[i], y[j], [-1]*(i)   + [0]*(j-i+1) + [1]*(N-j-1)) for j in range(i  ,N))
        yield from ((y[i], x[j], [-1]*(i+1) + [0]*(j-i-1) + [1]*(N-j))   for j in range(i+1,N))


# def column_factors():
#     """Alternative way to produce the column factors. Basically, using this function will
#        result in a row permutation with respect to the other definition of `column_factors`
#        above.
#        This definition here produces variable combinations in sequential form:
#        (x0,y0), (x0,y1), ..., (x0,y{N-1}), (x1,y0), (x1,y1), ..., ...
#     """
#     for i in range(N):
#         yield from ((y[j], x[i], [-1]*(j+1) + [0]*(i-j-1) + [1]*(N-i))   for j in range(0, i))
#         yield from ((x[i], y[j], [-1]*(i)   + [0]*(j-i+1) + [1]*(N-j-1)) for j in range(i, N))


def type_1(v1, v2, z, factor):
    return cos(v1 + v2 + factor*z)


def type_2(v1, v2, z, factor):
    return sin(v1 + v2 + factor*z)


def type_3(v1, v2, z, factor):
    return (1-abs(factor))*sin(z/2 + v1 - v2)  # 1-abs(factor) == (1+factor)%2   (does this help?)


M = [  # The matrix; will be of shape (N**2+1, 3*N) after building.
    [0, 0]*N + [1]*N,
]
for v1, v2, factors in column_factors():
    M.append(
          [type_1(v1, v2, z, f) for f in factors]
        + [type_2(v1, v2, z, f) for f in factors]
        + [type_3(v1, v2, z, f) for f in factors]
    )
M = Matrix(M)
assert M.shape == (N**2+1, 3*N)


with open('matrix.tex', 'w') as fh:
    print(latex(M), file=fh)


# === Mathematica ===

with open('matrix.nb', 'w') as fh:
    fh.write(
        str(M)
        .removeprefix('Matrix(')
        .removesuffix(')')
        .replace('[', '{')
        .replace(']', '}')
        .replace('sin(', 'Sin[')
        .replace('cos(', 'Cos[')
        .replace(')', ']')
    )

# ===================


# === SymPy ===

def my_iszero(x):
    """From: https://docs.sympy.org/latest/tutorial/matrices.html#zero-testing"""
    from sympy import exp
    print('.', end='', flush=True)  # track progress
    try:
        return x.rewrite(exp).simplify().is_zero
    except AttributeError:
        return None

# print(f'\nDet: {Matrix(M.tolist()[1:]).det().expand(trig=True).simplify()}')  # this computes forever
# print(f'\nRank: {M.rank(iszerofunc=my_iszero)}')  # this computes forever

# =============


# === Verify numerically ===

import numpy as np

rng = np.random.default_rng()
values = rng.uniform(low=0, high=100, size=2*N+1).tolist()  # x, y and z

M = M.subs(list(zip([*x, *y, z], values))).evalf().tolist()
M = np.array(M, dtype=float)

print(f'Rank: {np.linalg.matrix_rank(M)}')
print(f'Singular values (largest, smallest): {np.linalg.svd(M)[1][[0, -1]]}')

# ==========================

Exploring non-duplicated combinations of column factors

The following is the code for exploring non-duplicated rows in the factor-matrix $F_{kl}$ (it can be put before the # === Mathematica === block):

from collections import Counter
from pprint import pprint

counts = Counter('  '.join(f'{i: d}' for i in f) for _,_,f in column_factors())
print(
    'Number of non-duplicated rows:',
    sum(1 for f,c in counts.items() if c == 1)  # this equals 3*N-2
)
pprint(counts)

This is the output for $N=3$:

Number of non-duplicated rows: 7
Counter({'-1    0    1': 2,
         ' 0    1    1': 1,
         ' 0    0    1': 1,
         ' 0    0    0': 1,
         '-1    1    1': 1,
         '-1    0    0': 1,
         '-1   -1    1': 1,
         '-1   -1    0': 1})

This is the output for $N=4$:

Number of non-duplicated rows: 10
Counter({'-1   0   1   1': 2,
         '-1   0   0   1': 2,
         '-1  -1   0   1': 2,
         ' 0   1   1   1': 1,
         ' 0   0   1   1': 1,
         ' 0   0   0   1': 1,
         ' 0   0   0   0': 1,
         '-1   1   1   1': 1,
         '-1   0   0   0': 1,
         '-1  -1   1   1': 1,
         '-1  -1   0   0': 1,
         '-1  -1  -1   1': 1,
         '-1  -1  -1   0': 1})

Answer 1

I confirmed the claim for $N=3$ in the following way.
Using Somos' idea to express $\cos$ and $\sin$ by exponentials anywhere and to introduce variables $a_j=e^{i\,x_j},b_j=e^{i\,y_j},j=0,1,2$, $c=e^{i\,z/2}$, we obtain a matrix $M$ of rational functions in the 7 variables $a_j,b_j,j=0,1,2$ and $c$.
Unfortunately, pari/gp, which I use, seemed unable to compute the rank of $M$ in a reasonable amount of time as the rational functions appearing should be very complicated. Maybe other computer algebra systems can do it.
There is a trick to verify anyway that the rank of $M$ is at most 8. Observe that $x_0$ appears only in the first three rows of the matrix and therefore in the numerator of any $9\times9$-subdeterminant of $M$, the variable $a_0$ has at most degree 6. The same is true for the variables $a_1,a_2,b_0,b_1,b_2$. For simplicity, we only use that $z$ appears in each row of $M$ at most as a factor $z^2$ or $z^{-2}$ of some monomial, respectively. Hence the numerator of any $9\times9$-subdeterminant of $M$ has at most degree 36 in $z$.
It is well know that a polynomial in one variable of degree $n$ vanishing at $n+1$ points vanishes completely. Therefore we can verify that all $9\times9$-subdeterminants of $M$ vanish by checking this for $7\cdot7\cdot7\cdot7\cdot7\cdot7\cdot37= 4353013$ values of $(a_0,a_1,a_2,b_0,b_1,b_2,z)$. On my PC, pari/gp did this in about 8min, thus completing the proof.

For each higher $N$, this could also be done, but becomes more and more involved. In order to prove the conjecture for all $N$, another idea is needed.

Edit: The numerical experiments with pari/gp imply that all 9 columns of the $10\times9$ matrix given in the question are involved in a non-trivial linear combination of columns yielding 0. Finding a vector in its kernel cannot be too simple...

Edit 2: Here is my pari/gp code. The variable names are a bit different. Counterexamples, if any, are put to the file "fullrank.txt". There was none. Every 10000 tests, a number is printed as a sign of life.

M=[0,xa*ya,xa*yb,xa*yc,xb*ya/z^2,xc*ya/z^2,xb*yb/z^2,xb*yc/z^2,xc*yb/z^2,xc*yc/z^2;\
0,xa*ya*z^2,xa*yb,xa*yc,xb*ya*z^2,xc*ya,xb*yb,xb*yc,xc*yb/z^2,xc*yc/z^2;\
0,xa*ya*z^2,xa*yb*z^2,xa*yc,xb*ya*z^2,xc*ya*z^2,xb*yb*z^2,xb*yc,xc*yb*z^2,xc*yc;\
0,xa*ya,xa*yb,xa*yc,xb*ya/z^2,xc*ya/z^2,xb*yb/z^2,xb*yc/z^2,xc*yb/z^2,xc*yc/z^2;\
0,xa*ya*z^2,xa*yb,xa*yc,xb*ya*z^2,xc*ya,xb*yb,xb*yc,xc*yb/z^2,xc*yc/z^2;\
0,xa*ya*z^2,xa*yb*z^2,xa*yc,xb*ya*z^2,xc*ya*z^2,xb*yb*z^2,xb*yc,xc*yb*z^2,xc*yc;\
1,xa/ya*z,xa/yb*z,xa/yc*z,0,0,0,0,0,0;\
1,0,xa/yb*z,xa/yc*z,0,ya/xc*z,xb/yb*z,xb/yc*z,0,0;\
1,0,0,xa/yc*z,0,0,0,xb/yc*z,0,xc/yc*z];
for(i=1,3,for(j=2,10,M[i,j]=M[i,j]+1/M[i,j]));
for(i=4,6,for(j=2,10,M[i,j]=M[i,j]-1/M[i,j]));
for(i=7,9,for(j=2,10,if(M[i,j]!=0,M[i,j]=M[i,j]-1/M[i,j])))
L=M;za=0;file="fullrank.txt";
for(ia=1,7,La=subst(L,xa,ia);\
 for(ib=1,7,Lb=subst(La,xb,ib);\
  for(ic=1,7,Lc=subst(Lb,xc,ic);\
   for(ja=1,7,Ld=subst(Lc,ya,ja);\
    for(jb=1,7,Le=subst(Ld,yb,jb);\
     for(jc=1,7,Lf=subst(Le,yc,jc);\
      for(k =2,37,Lg=subst(Lf,z ,k );rr=matrank(Lg);\
       if(rr>8,write(file,Lg));\
       za=za+1;if(divrem(za,10000)[2]==0,print(za))\
)))))));

Edit 3: I found two symmetries of the original matrix for $N=3$.

For the first, replace all variables by their negative and multiply the first row and the columns containing $\sin$ with $-1$.

For the second, exchange simultaneously $x_2$ and $y_0$, $x_1$ and $y_1$, $x_0$ and $y_2$, $z$ and $-z$, the rows $2$ and $10$, $3$ and $8$, $5$ and $9$, the columns $1$ and $3$, $4$ and $6$, $7$ and $9$ and again multiply the columns containing $\sin$ and the first row by -1.

This would allow to reduce the number of computations by a factor of about 4.