The definition of Kruskal rank : maximum value of $k$ such that any $k$ columns of a matrix $\textbf{A}$ are linearly independent, then $k$ is the Kruskal rank of matrix $\textbf{A}$.
How is it different from rank of the matrix $\textbf{A}$ ?
Can you give an example where Kruskal rank and rank of a matrix are different.
$\endgroup$ 12 Answers
$\begingroup$The difference is that for the rank it is "there exist $k$ columns" not "any $k$ columns."
A matrix that contains an all zero-columns has Kruskal rank $0$. A matrix that contains the same column twice has Kruskal rank $1$ (or less).
Clearly such matrices can have a higher rank.
$\endgroup$ 2 $\begingroup$Kruskal rank or the spark of a given matrix $A$ is defined as "The smallest number of columns of $A$ that are linearly dependent". It is not the same thing as the rank. Consider a matrix $A$ with $rank(A)=r$. All we know for certain is that there exist a set of $r$ columns in $A$ which are linearly independent. We may still be able to find a set of $s\leq r$ columns which are linearly dependent, in which case we say that the $spark(A)=s$ and $A$ is not of full spark.
Consider the following example:
$$A=\left[ \begin{matrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 5 & 0 & 0 & 1 \end{matrix} \right]$$
$A$ is clearly full ranked with $rank(A)=3$ (It spans all $\mathbb R^3$ with the three last columns). However, the minimal set of dependent columns in $A$ is of size 2, namely the set: $$\left\{\left(\begin{matrix}0\\0\\0\\5 \end{matrix}\right),\left(\begin{matrix}0\\0\\0\\1 \end{matrix}\right)\right\}$$
In other words, following the spark definition, "The smallest number of columns of $A$ that are linearly dependent" is, in this case, 2. Hence, $spark(A)=2\leq rank(A)=3$ and $A$ is not of full rank.
A note about complexity:
In this case, we had to find the minimal number of columns which are linearly independent. obviously $2\leq rank(A)\leq (m+1)$, where $m$ is the number of rows in $A$. The left hand is because we need at least 2 columns for linear dependency and the right hand is because for a any matrix with columns in $\mathbb R^{m}$ any $(m+1)$ set of columns must be linearly dependent. So we may start by checking linear dependency for each pair of columns. In worst case we will have to move on to any 3 columns set and than any 4 column set and so on up to $(m+1)$ sized sets. And so, calculating the spark of a given matrix, is clearly difficult to obtain, compared to its rank, as it calls for a combinatorial search over all possible subsets of columns from $A$.
$\endgroup$ 1
