Question

数学达人们看过来：请教一下,如何解不等式方程组啊？

在有限域F(q)中(q为质数)，A为一个K*N的矩阵，x是一个N*1的未知列向量，并且q<K。
我想解不等式Ax≠0。
注意，这里不等于0指的是：
假设最终Ax=b,这里的Ax≠0的要求是b当中每一个元素都不等于零。

我的问题是：
1）如何知道Ax≠0有没有解？
2）如果有解的话：有没有多项式时间的算法能够求解出来的？如果没有多项式时间解法，能不能证明是NP的？
谢谢了~

Answer 1

这个题应该不能解出来；就算解存在，你也无法通过式子解出来；因为他的条件不够紧密；极有可能有多组解；当然，可以通过编程的方法来求；但笔试是无解的

追问

谢谢回复。
1）不需要例举出所有的解。如果有解的话，只需要找出来一个解就可以了。
2）如果有解的话，我需要的是一个算法。所以通常是通过编程实现的。

追答

3 7 7
2 7 2
3 3 2
4 7 4
A 2 6 6
3 7 7
7 4 5
4 4 2
5 3 3
2 2 3
2 3 2
2 3 4
X= 3
2
5
B= 58
30
25
46
48
58
54
30
36
25
22
32
我不知道你的b 是不是也要求在域内

追问

谢谢你的认真回复。
1）我需要的是一个通用的算法。也就是说我任意给一个A都能够解出x来的。
2）Ax=b, 根据有限域的定义，b一定是在这个域当中的。
3）你的例子中，K=12，我不知道你取的q是多少，但是肯定是大于12的。而我的题目中是要求q<K的。

追答

朋友；首先0不是质数，那么你说b在这个质数域中；那么b显然是不会为0的；其次我取的q=10；你看A就应该知道；他的元素全在10以内；再者Ax=b
A非零；x非零；b怎么可以去得到0啦；

Answer 2

因为F中只有有限个元素，其特征不可能是0，否则F将包含有理域R0，其元素将有无穷多个。设F的特征为质数p，于是，F包含素域RP为其子域：
Rp € F。
今设F含有q个元素。于是，F中有q-1个非0元素，这些元素在乘法下作成一个q-1元群，因而都适合方程
х^(q-1) = 1 .....（1）
由此推出的方程
х^q = х ....（2）
F中的元素0也适合。
所以Ax≠0没有解

追问

谢谢回复。不过没有看明白前面的一段跟“所以Ax≠0没有解 ”有什么因果关系。麻烦再讲详细一点，谢谢。

Answer 3

线性问题除了公理证明和计算推导以外，还可以从逻辑结构去解释，
对：如何知道Ax≠0有没有解，假设命题：若在有限域F(q)中(q为质数)，A为一个K*N的矩阵，x是一个N*1的未知列向量，并且q<K时存在Ax≠0，则Ax≠0有解。命题的逆否命题：若存在Ax≠0无解也就是AX=0有解则在有限域F(q)中(q为质数)，A为一个K*N的矩阵，x是一个N*1的未知列向量，并且q<K时有Ax=0
不是说的怎么样，只是给你一个解题思路
希望帮到你

Answer 4

如果A≠0(K*N)，设a_{ij}≠0，取x={0,...,1,...,0}T 仅第j 行为1.即为所求
若A=0, 显然无解
你这问题貌似有问题. 相当于查找指定项的时间, 是一次多项式时间

Answer 5

晕死，线性代数的问题嘛，等着啊，解出来就告诉你。

Answer 6

问老师呀