3
$\begingroup$

I have a matrix whose elements are complex or real numbers or expressions of complex-valued or real-valued functions. How can the row rank of that matrix be calculated over $\mathbb{Q}$? The row rank over $\mathbb{Q}$ is the number of rows that are linearly independent over $\mathbb{Q}$.

for example:

$$\left( \begin{array}{c} 1\\\sqrt2\\\sqrt3\\\sqrt6 \end{array}\right)$$

or

$$\left(\begin{array}{ccc} 1+x & \sqrt{2}x & e^x \\ 1 & \sqrt{2} & e^x \\ 0 & 0 & e^x \\ \end{array}\right)$$

Usually, Gaussian elimination is used. But what is the algorithm for Gaussian elimination over $\mathbb{Q}$?

How must the usual Gaussian elimination algorithm (see e.g. this short and easy program from the MathWorks Matlab forum) be changed for calculating the rank over $\mathbb{Q}$?

I also could calculate the Wronskian matrix or the Gramian matrix and calculate their determinant over $\mathbb{Q}$.
Example 2 is the Wronskian matrix of the first row of that matrix.

MAPLE has a procedure for calculating determinants over $\mathbb{Q}(i)$. See e.g. MAPLE: LinearAlgebra[Determinant] - method=rational. Is this only for choosing the fastest algorithm by the user?
What is the algorithm for determinant calculation over $\mathbb{Q}$ for matrices with complex elements?

I could build all combinations of up to three rows of the matrix and check if they are linearly dependent over $\mathbb{Q}$ because for up to 3 rows, I need to calculate only one coefficient of the linear combination and check if it is rational. But what is with larger matrices?

The answer to this questions help to solve the problem in Algebraic independence of the values of algebraic functions?.

$\endgroup$
  • $\begingroup$ Are you asking about the dimension of the $\Bbb{Q}$-span of the rows or .... what? So for example $$\pmatrix{1\cr\sqrt2\cr\sqrt3\cr\sqrt6\cr}$$ has row rank four? $\endgroup$ – Jyrki Lahtonen Oct 3 '19 at 18:42
  • $\begingroup$ If that is what you are looking for, I would first locate the $\Bbb{Q}$-span $V$ of the entries (on a good day that might be a field). Then locate a $\Bbb{Q}$-basis for $V$, replace all the matrix entries with their coordinates w.r.t. that basis. (multiplying the number of columns by $\dim_{\Bbb{Q}}V$). After that I have a matrix with rational entries, and can proceed normally. $\endgroup$ – Jyrki Lahtonen Oct 3 '19 at 18:50
  • $\begingroup$ So for example with the matrix in my first comment we have $V=\Bbb{Q}(\sqrt2,\sqrt3)$, an extension field of degree four. The entries of that matrix form a $\Bbb{Q}$-basis of $V$, meaning that after replacing them with their coordinate vectors I have the $4\times4$ identity matrix. $\endgroup$ – Jyrki Lahtonen Oct 3 '19 at 18:53
  • $\begingroup$ Sorry about the long comments. It is unclear to me whether my guess about what you wanted to ask is correct. $\endgroup$ – Jyrki Lahtonen Oct 3 '19 at 18:54
  • $\begingroup$ @ Jyrki Lahtonen Yes, the row rank of your matrix over $\mathbb{Q}$ is 4 - because none of the rows can be presented by a linear combination of the other rows with only coefficients from $\mathbb{Q}$. $\endgroup$ – IV_ Oct 3 '19 at 19:04
1
$\begingroup$

Here's what you can do. Let $A=(a_{ij})_{1\le i\le n, 1\le j\le m}$ be your matrix. I assume that all the entries are in some (not necessarily f.d.) extension field of $\Bbb{Q}$.

Let $V_j$ be the $\Bbb{Q}$-span of all the entries $a_{ij}, 1\le i\le n$. That is, the span of the entries on column $j$. Note that the space $V_j$ is finitely generated. Therefore we can find a basis $\mathcal{B}_j$ of $V_j$ over $\Bbb{Q}$. We can now obviously write all the entries $a_{ij}$, $1\le i\le n$, as $\Bbb{Q}$-linear combinations of numbers in $\mathcal{B}_j$.

Here's how you can answer your question using Gaussian elimination (over $\Bbb{Q}$):

  1. Replace column $j$ of $A$ with $|\mathcal{B}_j|$ columns simply by replacing each entry $a_{ij}$ with its vector of coordinates with respect to $\mathcal{B}_j$. Call the resulting matrix $\tilde{A}$.
  2. Perform the usual Gaussian elimination on $\tilde{A}$. Observe that as all the entries of $\tilde{A}$ are in $\Bbb{Q}$, this process will never take you outside of $\Bbb{Q}$.
  3. You can then read the row rank over $\Bbb{Q}$ of $A$ as the rank of $\tilde{A}$. This is because the bases $\mathcal{B}_j$ faithfully represent linear (in)dependencies over $\Bbb{Q}$. Similarly, you can find a basis for the row space of $A$ over $\Bbb{Q}$ simply by rewriting the $j$th blocks of the non-zero rows of the (reduced) row echelon form of $\tilde{A}$ as elements of $V_j$.
  4. As usual, the rank of $\tilde{A}$ is also equal to the size of its largest non-vanishing minor.

As a first example consider the one I proffered in the comments (to calibrate my understanding of the question): $$ A=\left(\begin{array}{c}1\\ \sqrt{2}\\ \sqrt{3}\\ \sqrt{6} \end{array}\right). $$ There is a single column. The space $V_1$ is the degree four extension field $F=\Bbb{Q}(\sqrt2,\sqrt3)$. From the first course on field extensions we know that $\mathcal{B}_1=\{1,\sqrt2,\sqrt3,\sqrt6\}$ is a $\Bbb{Q}$-basis of $F$. Writing the elements of $A$ in terms of this basis thus leads to the matrix $$ \tilde{A}=\left(\begin{array}{rrrr}1&0&0&0\\ 0&1&0&0\\ 0&0&1&0\\ 0&0&0&1 \end{array}\right). $$ We immediately see that $\tilde{A}$ is already in the row echelon form. Therefore $\tilde{A}$ has full rank, and we can conclude that the row rank of $A$ over $\Bbb{Q}$ is four.


As another example let's consider the matrix $$ B=\left(\begin{array}{rr} 1&1\\ \sqrt2&i\\ 3&1+i\\ 2+\sqrt2&2i\end{array}\right). $$ Here the entries on the first column are in the span of $\mathcal{B}_1=\{1,\sqrt2\}$ while the entries on the second column are in the span of $\mathcal{B}_2=\{1,i\}$. Replacing the entries of $B$ with their respective coordinate vectors gives us the matrix $$ \tilde{B}=\left(\begin{array}{rrrr} 1&0&1&0\\ 0&1&0&1\\ 3&0&1&1\\ 2&1&0&2 \end{array}\right). $$ Subtracting the appropriate multiples of the first row from the others gives $$ \rightarrow \left(\begin{array}{rrrr} 1&0&1&0\\ 0&1&0&1\\ 0&0&-2&1\\ 0&1&-2&2 \end{array}\right). $$ Further subracting the prescribed multiples of the second row from those below it yields $$ \rightarrow \left(\begin{array}{rrrr} 1&0&1&0\\ 0&1&0&1\\ 0&0&-2&1\\ 0&0&-2&1 \end{array}\right). $$ From here we see that the last row is a replica of the third, and will vanish in the next step. We can conclude that $\tilde{B}$ has rank $3$, and therefore also the the row rank of $B$ over $\Bbb{Q}$ is also $3$. Indeed, if we denote by $u_i$ the $i$th row of $B$, we easily see that $u_3-u_1=(2,i)=u_4-u_2,$ so the rows of $B$ are linearly dependent over $\Bbb{Q}$.


Running this algorithm will make it necessary to correctly identify the dimensions of the spaces $V_j$ (after which finding bases for them is usually straightforward). Some basic facts about algebraic extensions suffice to handle my example cases, but I do not know, whether such techniques will be available in the examples that interest you the most.

In the second example from the question the space $V_1$ consists of degree one polynomials with coefficients from $\Bbb{Q}$, so $\mathcal{B}_1=\{1,x\}$. We see that $V_2=\sqrt{2}V_1$, so we can use $\mathcal{B}_2=\sqrt2\mathcal{B}_1$. Finally we see that $V_3$ is the 1-dimensional space spanned by $e^x$. For this matrix, call it $C$, we thus get $$ \tilde{C}=\left(\begin{array}{rrrrr} 1&1&0&1&1\\ 1&0&1&0&1\\ 0&0&0&0&1\end{array}\right). $$ Looking at columns $2,3$ and $5$ we immediately see that $\tilde{C}$ has full rank. Therefore the row rank of $C$ over $\Bbb{Q}$ is also $3$.

$\endgroup$
1
$\begingroup$

I want to change the Gaussian elimination algorithm for calculating the rank over $\mathbb{Q}$.

You can't, for things like the matrix $$ \begin{bmatrix} 1 \\ \sqrt{2} \end{bmatrix} $$ since that algorithm depends on the fact that vectors are represented as tuples of field entries.

That matrix happens to have rank $2$: the dimension of the $\mathbb{Q}$ subspace spanned by $(1, \sqrt{2})$ in the (infinite dimensional) $\mathbb{Q}$ vector space $\mathbb{C}$.

Edit in response to edited question.

This quote is new:

MAPLE has a procedure for calculating determinants over $\mathbb{Q}(i)$. But what is the algorithm for determinant calculation over $\mathbb{Q}$?

That makes no sense. The determinant of a matrix is a polynomial expression in the matrix elements, which must belong to some ring. The determinant "over $\mathbb{Q}(i)$" probably refers to a calculation where the elements are members of that field.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.