Skip to main content
Missing math mode
Source Link
LSpice
  • 12.9k
  • 4
  • 45
  • 69

Here is an example I encountered in my research:

Let $A=(a_{n, m})$ be an $N\times M$ matrix such that for all $n$ there exists $k=k(n)$ such that $a_{n,m}=0$ if $m\neq k, k+1$, that is in every row we have at most two non-zero numbers and they go one after the other, and assume that we want to know if $A$ is injective, that is whether there exists a non-zero vector v$v$ such that $Av=0$. Then it is not terribly difficult to convince yourself that this can be done by only looking at which elements of the matrix $A$ are non-zero and which pairs of rows of $A$ are linearly independent and do some fairly simple combinatorics depending on this.

However, if we say that $a_{n, m}=0$ if $m\neq k, k+1, k+2$, that is if we allow for 3 consecutive non-zero elements, then the problem becomes at least as hard as the one of determining whether the Jacobi matrix is non-singular which is a subject of dozens of books and hundredths of papers, and in particular is a very difficult problem to approach analytically.

Here is an example I encountered in my research:

Let $A=(a_{n, m})$ be an $N\times M$ matrix such that for all $n$ there exists $k=k(n)$ such that $a_{n,m}=0$ if $m\neq k, k+1$, that is in every row we have at most two non-zero numbers and they go one after the other, and assume that we want to know if $A$ is injective, that is whether there exists a non-zero vector v such that $Av=0$. Then it is not terribly difficult to convince yourself that this can be done by only looking at which elements of the matrix $A$ are non-zero and which pairs of rows of $A$ are linearly independent and do some fairly simple combinatorics depending on this.

However, if we say that $a_{n, m}=0$ if $m\neq k, k+1, k+2$, that is if we allow for 3 consecutive non-zero elements, then the problem becomes at least as hard as the one of determining whether the Jacobi matrix is non-singular which is a subject of dozens of books and hundredths of papers, and in particular is a very difficult problem to approach analytically.

Here is an example I encountered in my research:

Let $A=(a_{n, m})$ be an $N\times M$ matrix such that for all $n$ there exists $k=k(n)$ such that $a_{n,m}=0$ if $m\neq k, k+1$, that is in every row we have at most two non-zero numbers and they go one after the other, and assume that we want to know if $A$ is injective, that is whether there exists a non-zero vector $v$ such that $Av=0$. Then it is not terribly difficult to convince yourself that this can be done by only looking at which elements of the matrix $A$ are non-zero and which pairs of rows of $A$ are linearly independent and do some fairly simple combinatorics depending on this.

However, if we say that $a_{n, m}=0$ if $m\neq k, k+1, k+2$, that is if we allow for 3 consecutive non-zero elements, then the problem becomes at least as hard as the one of determining whether the Jacobi matrix is non-singular which is a subject of dozens of books and hundredths of papers, and in particular is a very difficult problem to approach analytically.

Source Link
Aleksei Kulikov
  • 6.5k
  • 1
  • 19
  • 28

Here is an example I encountered in my research:

Let $A=(a_{n, m})$ be an $N\times M$ matrix such that for all $n$ there exists $k=k(n)$ such that $a_{n,m}=0$ if $m\neq k, k+1$, that is in every row we have at most two non-zero numbers and they go one after the other, and assume that we want to know if $A$ is injective, that is whether there exists a non-zero vector v such that $Av=0$. Then it is not terribly difficult to convince yourself that this can be done by only looking at which elements of the matrix $A$ are non-zero and which pairs of rows of $A$ are linearly independent and do some fairly simple combinatorics depending on this.

However, if we say that $a_{n, m}=0$ if $m\neq k, k+1, k+2$, that is if we allow for 3 consecutive non-zero elements, then the problem becomes at least as hard as the one of determining whether the Jacobi matrix is non-singular which is a subject of dozens of books and hundredths of papers, and in particular is a very difficult problem to approach analytically.

Post Made Community Wiki by Aleksei Kulikov