判断数域上s个方程的n元线性方程组有无解，有解时解集的结构

本文主要是介绍判断数域上s个方程的n元线性方程组有无解，有解时解集的结构，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

以向量之间的关系判断是否有解，以及解的情况

具体说明都放在类和方法的注释上。

2. 列向量组

import java.util.*;/*** 利用向量之间的关系判断s个方程的n元线性方程组有没有解，若有无穷多解，给出解集的结构** @author cqh* @date 2023/12/15 12:30*/
/*
取出 a1,...,an 它的线性无关组 a1,...,ar，这个无关组要能够表出向量组的所有向量
a1,...,ar 肯定能被线性表出，那除此之外的向量呢？
r < j <= n，取出向量 aj，则 aj 可由 a1,...,ar 线性表出的充分必要条件是 a1,...,ar,aj 线性相关从向量组中取出一个部分的线性无关组，若从向量组的其余向量中任取一个向量都与部分组线性相关，称部分组为极大线性无关组
取得向量组 a1,a2,...,an 的极大线性无关组 maxLine，定义 rank{a1,a2,...,an} = maxLine.size
当 maxLine.size == n 时，a1,a2,...,an 的极大线性无关组就是自身，则 a1,a2,...,an 线性无关
即 a1*x1+...+an*xn = 0 只有零解，以 a1,...,an 为列向量的系数矩阵的行列式不等于0，a1*x1+...+an*xn = b 若有解，为唯一解(1)maxLine.size == n 时若 maxLine 与 B 线性无关，无解若 maxLine 与 B 线性相关，唯一解(2)maxLine.size < n 时若 maxLine 与 B 线性无关，无解若 maxLine 与 B 线性相关，无穷多解*/
public class VectorDisX {public static void main(String[] args) {/*1a + 6b + 3c + 2d = 22a + 2b + 1c + 4d = 13a + 1b + 2c + 1d = 4*/// a1,a2,...an 是列向量组，s维，a[i].length 为方程个数s，A.length 为未知数个数n，不限制 s 一定要等于 n// A 是行列颠倒的，第i列是第i个方程的系数Rational[] a1 = {new Rational(1), new Rational(2), new Rational(3)};Rational[] a2 = {new Rational(6), new Rational(2), new Rational(1)};Rational[] a3 = {new Rational(3), new Rational(1), new Rational(2)};Rational[] a4 = {new Rational(2), new Rational(4), new Rational(1)};Rational[] B = {new Rational(2), new Rational(1), new Rational(4)};Rational[][] A = {a1, a2, a3, a4};List list = disX(A, B);print(list);// 获取一个解集Rational[] X = getX(list, 20);if (X != null) {System.out.println("要验证的解集 X = " + Arrays.toString(X));verify(A, B, X);}}/*** 验证 X 是否是方程组的解* @param A 系数矩阵* @param B 常数项* @param X 待验证的解*/public static void verify(Rational[][] A, Rational[] B, Rational[] X) {int n = A.length;int s = A[0].length;for (int i = 0; i < s; i++) {Rational r = Rational.zero;for (int j = 0; j < n; j++) {// j 从 0 到 n，求方程左边 n 个乘积项之和：Σ x[j] * a[j][i]r = r.add(X[j].mul(A[j][i]));}// 方程左边等于方程右边System.out.println(r + " = " + B[i]);if (!r.equals(B[i])) {System.out.println("第 " + (i + 1) + " 个方程结果错误！");}}}/*** 获取方程组的某个解集* @param result 包含解集信息的集合* @param max 无穷多解时，k[i] ∈ [0, max)* @return 方程组的解*/public static Rational[] getX(List result, int max) {Solution solution = (Solution) result.get(SOLUTION);switch (solution) {case UNIQUE :// 方程有唯一解时return (Rational[]) result.get(PARTICULAR);case INFINITELY_MANY:// 方程有无穷多解时Rational[] gam = (Rational[]) result.get(PARTICULAR);Rational[][] eta = (Rational[][]) result.get(FUNDAMENTAL);// K = {k1,k2,...}，k[i]为随机整数Rational[] K = new Rational[eta.length];Rational[] X = new Rational[gam.length];int index = 0;random(K, max);System.out.println("令 K = " + Arrays.toString(K));for (int j = 0; j < gam.length; j++) {Rational xj = gam[j];for (int ei = 0; ei < eta.length; ei++) {// x[j] = gam[j] + eta[0][j] * k[0] + eta[1][j] * k[1] +...xj = xj.add(eta[ei][j].mul(K[ei]));}X[index++] = xj;}return X;default:return null;}}// 随机数生成private static final Random random = new Random();private static void random(Rational[] arr, int max) {for (int i = 0; i < arr.length; i++) {arr[i] = new Rational(random.nextInt(max));}}/*** 用于查找不为0的元素* 指明查找方向：向右，向下*/public enum Orient {RIGHT, DOWN}/*** 解集情况：无解，唯一解，无穷多解*/public enum Solution {NO, UNIQUE, INFINITELY_MANY}/*** 解集情况*/public static final int SOLUTION = 0;/*** 特解*/public static final int PARTICULAR = 1;/*** 基础解系*/public static final int FUNDAMENTAL  = 2;/*** 打印解集情况* @param solution 包含解集信息的集合*/public static void print(List solution) {Rational[] gam;Rational[][] eta;switch ((Solution)solution.get(SOLUTION)) {case UNIQUE:System.out.print("唯一解：");gam = (Rational[]) solution.get(PARTICULAR);System.out.println(Arrays.toString(gam));break;case INFINITELY_MANY:System.out.println("无穷多解");gam = (Rational[]) solution.get(PARTICULAR);eta = (Rational[][]) solution.get(FUNDAMENTAL);StringBuilder builder = new StringBuilder();int s = gam.length;int n = eta.length;for (int i = 0; i < s; i++) {builder.append("x" + (i+1) + " = ");builder.append(gam[i]);builder.append(" + ");for (int j = 0; j < n; j++) {builder.append(eta[j][i]);builder.append(" * k" + (j+1));if (j != n-1) {builder.append(" + ");}}builder.append("\n");}builder.append("k1,k2,...,kn ∈ Q");System.out.println(builder);break;default:System.out.println("无解");}}// 确保 A 是 s*n 矩阵，B 的长度为 sprivate static void checkLength(Rational[][] A, Rational[] B) {int n = A.length;int s = A[0].length;for (int i = 1; i < n; i++) {if (s != A[i].length) {throw new ArrayIndexOutOfBoundsException("向量长度应为" + s + ", 而a" + (i+1) + "长度为" + A[i].length);}}if (B.length != s) {throw new ArrayIndexOutOfBoundsException("B的长度应为" + s);}}/*** 获取矩阵A的列向量组的极大线性无关组* @param A 系数矩阵* @return 矩阵的列向量组的极大线性无关组*/public static List<Rational[]> getMaxLine(Rational[][] A) {int n = A.length;List<Rational[]> maxLine = new ArrayList<>();for (int i = 0; i < n; i++) {// 如果向量 A[i] 与向量组 maxLine 线性无关，则添加进 maxLineif (isIndependent(maxLine, A[i])) {maxLine.add(A[i]);}}return maxLine;}// 获取矩阵A的列向量组的极大线性无关组@Deprecatedprivate static List<Rational[]> getMaxLine2(Rational[][] A) {int n = A.length;int i = 0;List<Rational[]> maxLine = new ArrayList<>();// 将非零向量添加进 maxLine，之后慢慢扩充至极大线性无关组while (i < n) {if (!isZero(A[i])) {maxLine.add(A[i]);break;}i++;}// 全是零向量if (maxLine.size() == 0) {return null;}// 若 ai 与向量组 maxLine 线性无关，则添加进 maxLine// 最终 maxLine 为向量组 a1,...,an 的极大线性无关组for (i = i + 1; i < n; i++) {if (isIndependent(maxLine, A[i])) {maxLine.add(A[i]);}}return maxLine;}/*** 获取解集情况* @param A 系数矩阵* @param B 常数项* @return 包含解集情况信息的集合*/public static List disX(Rational[][] A, Rational[] B) {checkLength(A, B);int n = A.length;List X = new ArrayList(3);List<Rational[]> maxLine = getMaxLine(A);int r = maxLine.size();// 如果线性无关，则无解boolean noExplain = isIndependent(maxLine, B);if (noExplain) {X.add(SOLUTION, Solution.NO);} else {// 如果线性相关，B 可由线性组 a1,a2,...,an 线性表出，有唯一解或无穷多解// 若 r = n，则是唯一解；否则是无穷多解Solution solution = (r == n) ? Solution.UNIQUE : Solution.INFINITELY_MANY;X.add(SOLUTION, solution);disaggregation(A, B, X, r);}return X;}// 获取解集信息@Deprecatedprivate static List disX2(Rational[][] A, Rational[] B) {checkLength(A, B);int n = A.length;List X = new ArrayList(3);List<Rational[]> maxLine = getMaxLine2(A);// a1、a2、...、an 都是零向量if (maxLine == null || maxLine.size() == 0) {// 如果 b 不为零向量，则无解if (!isZero(B)) {X.add(SOLUTION, Solution.NO);} else {// 如果 b 为零向量，则无穷多解X.add(SOLUTION, Solution.INFINITELY_MANY);// 特解为 (0,0,...0)Rational[] gam = new Rational[n];for (int gi = 0; gi < n; gi++) {gam[gi] = Rational.zero;}// 基础解系为：(1,0,...,0)、(0,1,0,...0)...、(0,...0,1)Rational[][] eta = new Rational[n][n];for (int ei = 0; ei < n; ei++) {for (int ej = 0; ej < n; ej++) {if (ei == ej) {eta[ei][ej] = Rational.one;} else {eta[ei][ej] = Rational.zero;}}}X.add(PARTICULAR, gam);X.add(FUNDAMENTAL, eta);}return X;}// 若极大线性无关组中的向量数量等于未知量个数，即 rank{a1,...,an} = n// a1,...,an 自身为极大线性无关组if (maxLine.size() == n) {// B,a1,a2...,an 线性无关，则 B 不能由 a1,...,an 线性表出，无解if (isIndependent(maxLine, B)) {X.add(SOLUTION, Solution.NO);} else {// B,a1,...,an 线性相关，B 可以由 a1,...,an 线性表出，且表出方式唯一，唯一解X.add(SOLUTION, Solution.UNIQUE);disaggregation(A, B, X, n);}return X;}// 若 rank{a1,...,an} < n，极大线性无关组 list 不是自身，a1,...,an 线性相关// a1,...,an 可由向量组 list 线性表出// B 由 a1,...,an 线性表出等价于 B 由 list 线性表出// B,list 线性无关, B 不能由 list 表出，无解if (isIndependent(maxLine, B)) {X.add(SOLUTION, Solution.NO);} else {// B,list 线性相关, B 可以由 list 表出，无穷多解X.add(SOLUTION, Solution.INFINITELY_MANY);disaggregation(A, B, X, maxLine.size());}return X;}// 拷贝时行列互换private static void copy(Rational[][] oldArr, Rational[][] newArr) {for (int i = 0; i < oldArr.length; i++) {for (int j = 0; j < oldArr[i].length; j++) {newArr[j][i] = oldArr[i][j];}}}// 拷贝 old1 到 newArr 时行列互换private static void copy(List<Rational[]> old1, Rational[] old2, Rational[][] newArr) {int s = old1.get(0).length;int n = old1.size() + 1;for (int j = 0; j < n - 1; j++) {for (int i = 0; i < s; i++) {newArr[i][j] = old1.get(j)[i];}}for (int i = 0; i < s; i++) {newArr[i][n-1] = old2[i];}}private static void copy(Rational[] oldArr, Rational[] newArr) {for (int i = 0; i < oldArr.length; i++) {newArr[i] = oldArr[i];}}// 交换矩阵 A、B 的第 index 和第 i 行，j 是交换的两行的起始元素下标private static void swap(Rational[][] A, Rational[] B, int index, int i, int j) {Rational temp = B[i];B[i] = B[index];B[index] = temp;swap(A, index, i, j);}private static void swap(Rational[][] A, int index, int i, int j) {int n = A[0].length;for (int l = j; l < n; l++) {Rational temp = A[i][l];A[i][l] = A[index][l];A[index][l] = temp;}}// 从第 j 个元素开始，第 index 行加上第 i 行的固定倍数，使其起始位置元素值为0private static void addRow(Rational[][] A, Rational[] B, int index, int i, int j) {Rational d = A[index][j].div(A[i][j]);B[index] = B[index].sub(B[i].mul(d));// 相加后 A[index][j] 的值会变，所以倍数的计算要放在首行addRow(A, index, i, j);}private static void addRow(Rational[][] A, int index, int i, int j) {int n = A[0].length;Rational d = A[index][j].div(A[i][j]);for (int l = j; l < n; l++) {A[index][l] = A[index][l].sub(A[i][l].mul(d));}}/*** 将解集信息存入集合中* @param A_ 系数矩阵* @param B_ 常数项* @param X 包含解集信息的集合* @param r 系数矩阵的列向量组的秩*/public static void disaggregation(Rational[][] A_, Rational[] B_, List X, int r) {int i = 0;int j = 0;int index = -1;int s = A_[0].length;int n = A_.length;Rational[][] A = new Rational[s][n];Rational[] B = new Rational[s];copy(A_, A);copy(B_, B);// 将 A 化为阶梯形矩阵while (i < s && j < n) {// 找到第 j 列中不为 0 的元素，其元素行标赋给 indexwhile (j < n && (index = find(A, i, j, Orient.DOWN)) == -1) {j++;}// 直至最后一列都是零元素if (j == n) {break;}// 若找到了非零元素，则将第 index 与第 i 行对换，保证 A[i][j] 不为 0if (index != i) {swap(A, B, index, i, j);}// 将第 (i, s) 行加上第 i 行的倍数，将这些行的第 j 列元素置为 0for (int k = i+1; k < s; k++) {addRow(A, B, k, i, j);}i++;j++;}// 将主元所在列其余元素置为0，注意主元不一定为1，不是简化行阶梯矩阵i = r - 1;index = r;// 记录每个主元的列标int[] primary = new int[r];while (i >= 0) {// 找到第 i 行中不为 0 的元素，其元素行标赋给 j，则 A[i][j] 是主元while (i >= 0 && (j = find(A, i, i, Orient.RIGHT)) == -1) {i--;}if (i < 0) {break;}primary[--index] = j;// 将第 [0, i) 行加上第 i 行的倍数，将这些行的第 j 列元素置为 0for (int k = 0; k < i; k++) {addRow(A, B, k, i, j);}i--;}index = 0;// 记录自由未知量的下标int[] free = new int[n-r];for (j = 0; j < n; j++) {if (!contains(primary, j)) {free[index++] = j;}}// 讨论解集的结构/*非零行个数 r = 2，未知量个数 n = 4，自由量是 x[2] 和 x[3]1  0  a0  a1    b00  1  a2  a3    b1x[0] = -a0*x[2] - a1*x[3] + b0x[1] = -a2*x[2] - a3*x[3] + b1取方程的一个任意解：{c0,c1,c2,c3} 代入此方程c0 = -a0*c2 - a1*c3 + b0c1 = -a2*c2 - a3*c3 + b1c2 =   1*c2 +  0*c3 + 0c3 =   0*c2 +  1*c3 + 0X = (c0,c1,c2,c3) = (-a0,-a2,1,0)*c2 + (-a1,-a3,0,1)*c3 + (b0,b1,0,0)令 eta[0] = (-a0,-a2,1,0)，eta[1] = (-a1,-a3,0,1)，gam = (b0,b1,0,0)eta[i] 和 gam 的长度都为 n，eta 的长度为 n-rX = eta[0]*k1 + eta[1]*k2 + gam，k1，k2 可取任意值（域内）则任意一个解集 X 都可以由 eta[0]、eta[1]、gam 线性表出*//*eta 的求法令自由量分别取 (1,0,...,0), (0,1,0,...,0),...,(0,...,0,1) 这 n-r 组值并分别代入对应的齐次线性方程组求得主变量，并将 n-r 组 n 个未知量存入 eta 中gam 的求法令自由量为 0，代入方程得到主变量，并将 n 个未知量存入 gam 中*/// 讨论 eta 中自由量的取值/*令自由量分别取线性无关的 n-r 组值如 (d1,0,...,0), (0,d2,0,...,0),...,(0,...,0,dn)，di ≠ 0代入到齐次线性方程组得：(x[0],x[1],x[2],x[3]) = (-a0*d1,-a2*d1,d1,0) = (-a0,-a2,1,0)*d1 = eta[0]*d1(x[0],x[1],x[2],x[3]) = (-a1*d2,-a3*d2,0,d2) = (-a1,-a3,0,1)*d2 = eta[1]*d2X = (eta[0]*d1)*u1 + (eta[1]*d2)*u2 + gam令 u1 = k1/d1，u2 = k2/d2X = (eta[0]*d1)*(k1/d1) + (eta[1]*d2)*(k2/d2) + gam= (eta[0]*d1)*k1 + (eta[1]*d2)*k2 + gam= eta[0]*k1 + eta[1]*k2 + gam则任意一个解集 X 都可以由 eta[0]*d1、eta[1]*d2、gam 线性表出令自由量取 (d1,d2)、(d3,d4)(x[0],x[1],x[2],x[3]) = (-a0*d1-a1*d2,-a2*d1-a3*d2,d1,d2) = (-a0,-a2,1,0)*d1 + (-a1,-a3,0,1)*d2 = eta[0]*d1 + eta[1]*d2(x[0],x[1],x[2],x[3]) = (-a0*d3-a1*d4,-a2*d3-a3*d4,d3,d4) = (-a0,-a2,1,0)*d3 + (-a1,-a3,0,1)*d4 = eta[0]*d3 + eta[1]*d4X = eta[0]*k1 + eta[1]*k2 + gam ①X = (eta[0]*d1 + eta[1]*d2) * u1 + (eta[0]*d3 + eta[1]*d4) * u2 + gam ②= eta[0]*(d1*u1+d3*u2) + eta[1]*(d2*u1+d4*u2) + gam无论 k1、k2 任取何值时，下列方程总有解，u1=?，u2=?d1*u1 + d3*u2 = k1d2*u1 + d4*u2 = k2只有当系数行列式 |A| = d1*d4 - d3*d2 ≠ 0 时，此方程才有唯一解对应的齐次线性方程组：d1*u1 + d3*u2 = 0d2*u1 + d4*u2 = 0写成：(d1,d2)*u1 + (d3,d4)*u2 = 0，|A|≠0时，只有零解，则 (d1,d2)、(d3,d4) 线性无关存在一组值(c1,c2)，使得 (k1,k2) = (d1,d2)*c1 + (d3,d4)*c2，则 c1、c2 就是方程的解即 (k1,k2) 能由 (d1,d2)、(d3,d4) 线性表出任一向量 K = (k1,k2) 都可以由 (d1,d2)、(d3,d4) 线性表出则向量组 (1,0)、(0,1) 也可以由 (d1,d2)、(d3,d4) 线性表出2 = rank{(1,0)、(0,1)} <= rank{(d1,d2)、(d3,d4)}rank{(d1,d2)、(d3,d4)} = 2，从而 (d1,d2)、(d3,d4) 线性无关当(d1,d2)、(d3,d4) 线性无关时，任意一个解 X 都能由 eta[0]*d1+eta[1]*d2, eta[0]*d3+eta[1]*d4, gam 线性表出所以求 eta 时可以取线性无关的 n-r 组值，不一定非要是 1,0 组成的*/// 讨论 gam 中自由量的取值/*令自由量取 (d1,d2)，代入到方程组得：(x[0],x[1],x[2],x[3]) = (-a0*d1-a1*d2+b0, -a2*d1-a3*d2+b1, d1, d2)= (-a0,-a2,1,0)*d1 + (-a1,-a3,0,1)*d2 + (b0,b1,0,0)= eta[0]*d1 + eta[1]*d2 + gamX = eta[0]*u1 + eta[1]*u2 + (eta[0]*d1 + eta[1]*d2 + gam)= eta[0]*(u1+d1) + eta[1]*(u2+d2) + gam令 u1 = k1-d1，u2 = k2-d2X = eta[0]*k1 + eta[1]*k2 + gam无论令自由量取何值，X 都能由 eta[0], eta[1], (eta[0]*d1+eta[1]*d2+gam) 线性表出所以求 gam 时，不限制一定要自由量为 0*/// 讨论主变量 x[j] 的取值，j = primary[i] 是第 i 行主元的列标/*3 2 1 4     33x[0] + 2x[1] + 1x[2] + 4x[3] = 3x[0] = 3/3 - (2/3)x[1] - (1/3)x[2] - (4/3)x[3]?[primary[i]] = x[primary[i]] = (b[i] - Σ A[i][free[l]] * ?[free[l]]) / A[i][primary[i]]，i ∈ [0,r)Σ 是对 l 从 0 到 free.length-1 求和，? 是存所有未知量值的数组(1) 求 gam，令自由未知量等于(0,...,0)，存入 ? 数组中，求和中共有 free.length 个乘积项，每个乘积项中的因式 ?[free[l]] 为 0，则乘积为 0，求和项为 0则主变量的值 x[primary[i]] = b[i] / A[i][primary[i]](2) 求 eta，令自由量取值 (1,0,...,0)，只有当 l = 0 时的第一个乘积项的 ?[free[0]] = 1，其余乘积项都为零对应的齐次线性方程组的主变量值为x[primary[i]] = (-A[i][free[0]] * ?[free[0]]) / A[i][primary[i]]= (-A[i][free[0]]) / A[i][primary[i]]令自由量取值 (0,1,0,...,0)，则是只有第二个乘积项的值不为0，?[free[0]]、?[free[2]]、... 都为 0x[primary[i]] = (-A[i][free[1]]) / A[i][primary[i]]令 eta[0] 保存 (1,0,...,0)，第1个自由量为1，其余都为0，?[free[0]] = eta[0][free[0]] = 1令 eta[1] 保存 (0,1,0,...,0)，第2个自由量为1，其余都为0，?[free[1]] = eta[1][free[1]] = 1...则 eta[ei] 中，第 ei+1 个自由量值为 1，其余都为 0eta[ei][free[ei]] = 1，eta[ei][free[除ei外的下标]] = 0for(int i = 0; i < r; i++) {eta[ei][primary[i]] = -A[i][free[ei]] / A[i][primary[i]]}*/// 下面为了简化运算，自由量只取 0 或 1// 求某个特定解，将它们存入数组 gamRational[] gam = new Rational[n];for (int fi = 0; fi < free.length; fi++) {// 先存入值为 0 的自由量gam[free[fi]] = Rational.zero;}/*阶梯形矩阵如下：3 0 0 0     30 0 4 0     5可得：x[0] = 3/3，x[2] = 5/4，primary记录每行主元列标：[0, 2]x[2] = x[primary[1]] = B[1] / A[1][primary[1]]j = primary[i] 是第 i 行主元的列标，也是以此主元为系数的未知量的下标 x[j]A[i][j] 是第 i 行主元的值，x[j] 的值为 B[i]/A[i][j]*/for (int pi = 0; pi < primary.length; pi++) {// 再存入主变量gam[primary[pi]] = B[pi].div(A[pi][primary[pi]]);}// 令 n-r 个自由量分别取 (1,0,...,0)、(0,1,...,0)、...、(0,...,0,1) 这 n-r 组数，求得对应齐次线性方程组的解Rational[][] eta = new Rational[n-r][n];for (int ei = 0; ei < eta.length; ei++) {for (int fi = 0; fi < free.length; fi++) {if (ei == fi) {eta[ei][free[fi]] = Rational.one;} else {eta[ei][free[fi]] = Rational.zero;}}/*0 3 0 2     0可得：3 * x[1] + 2 * x[3] = 0，primary：[1]，free：[0, 2, 3]两边同时除以 3 得：x[1] = -(2/3) * x[3]x[0]、x[2]、x[3] 取 (1, 0, 0) 时，x[1] = x[primary[0]] = 0，值为第 0 行的 x[0] 的系数除以第 0 行的主元的相反数x[0]、x[2]、x[3] 取 (0, 1, 0) 时，x[1] = 0，值为第 0 行的 x[2] 的系数除以第 0 行的主元的相反数x[0]、x[2]、x[3] 取 (0, 0, 1) 时，x[1] = -2/3，值为第 0 行的 x[3] 的系数除以第 0 行的主元的相反数ei 为 (0,...,0,1,0,...,0) 中 1 的下标x[j] = -A[i][free[ei]] / A[i][j]*/for (int pi = 0; pi < primary.length; pi++) {eta[ei][primary[pi]] = A[pi][free[ei]].sign().div(A[pi][primary[pi]]);}}X.add(PARTICULAR, gam);X.add(FUNDAMENTAL, eta);}// 若 arr 包含 num，则返回 trueprivate static boolean contains(int[] arr, int num) {for (int i = 0; i < arr.length; i++) {if (num == arr[i]) {return true;}}return false;}/*** 根据模式查找，返回非零元素的下标* @param A 待查的矩阵* @param i 起始位置的行标* @param j 起始位置的列标* @param o 查找模式。down是向下查找，行标变；right是向右查找，列标变* @return 返回非零元素的下标。向下查找时，返回非零元素的行标；向右查找时，返回非零元素的列标。*         若没有查找到，返回-1*/public static int find(Rational[][] A, int i, int j, Orient o) {int s = A.length;int n = A[0].length;// 向下查找不为 0 的元素的行标，或向右查找不为 0 的元素的列标switch (o) {case DOWN:while (i < s) {if (!Rational.zero.equals(A[i][j])) {break;}i++;}if (i == s) {return -1;}return i;case RIGHT:while (j < n) {if (!Rational.zero.equals(A[i][j])) {break;}j++;}if (j == n) {return -1;}return j;default:return -1;}}/*** 若 a 与向量组 maxLine 线性无关，则返回 true* @param maxLine 线性无关组* @param a 某个向量* @return 若向量组 a,maxLine 线性无关，则返回 true，否则返回 false*/public static boolean isIndependent(List<Rational[]> maxLine, Rational[] a) {boolean isZero = isZero(a);// 有零向量，必定线性相关if (isZero) {return false;}boolean isEmpty = maxLine == null || maxLine.isEmpty();// 若集合为空，且 a 不等于零向量，则线性无关if (isEmpty)  {return true;}int s = maxLine.get(0).length;int n = maxLine.size() + 1;// s < n 必有非零解，则线性相关// 超过 s 个 s 维向量必线性相关if (s < n) {return false;}// 将 maxLine 与 a 合并Rational[][] A = new Rational[s][n];copy(maxLine, a, A);/*若 maxLine 与 a 线性无关，则方程组 x1*maxLine + x2*a = 0 只有零解即以 maxLine、a 为列(行)向量组的矩阵的行列式不等于0利用两行互换、一行的倍数到另一行上，行列式的绝对值不改变的性质将行列式转为上三角形行列式，将主对角线上的元素相乘，得到行列式的绝对值若绝对值不为0，则线性无关，返回true，否则就返回false*/int i = 0;int j = 0;while (i < s && j < n) {// 如果 A[i][j] 为 0// 找到第 j 列中不为 0 的元素的行标 k，并将第 i 行与第 k 行对换if (Rational.zero.equals(A[i][j])) {for (int k = i + 1; k < s; k++) {if (!Rational.zero.equals(A[k][j])) {swap(A, k, i, j);break;}}}// 如果此列元素全为 0，行列式值为 0，线性相关if (Rational.zero.equals(A[i][j])) {return false;}// 将第 (i, s) 行加上第 i 行的倍数，将这些行的第 j 列元素置为 0for (int k = i+1; k < s; k++) {addRow(A, k, i, j);}i++;j++;}// 经过上述过程后，前 n 行已转为上三角行列式，后 s-n 行全为零行// 将主对角线上的元素相乘，得到的 l 为行列式的值// 若 l = 0，则线性相关，否则线性无关Rational l = Rational.one;for (i = 0; i < n; i++) {l = l.mul(A[i][i]);}if (Rational.zero.equals(l)) {return false;}return true;}/*** 如果向量 a 的每个分量都为 0，则返回 true* 规定 {} 为零向量* @param a 向量* @return 若向量的每个元素都为0，或向量长度为0，则返回 true；否则返回 false*/public static boolean isZero(Rational[] a) {for (int i = 0; i < a.length; i++) {if (!Rational.zero.equals(a[i])) {return false;}}return true;}// 将解集信息存入集合中@Deprecatedprivate static void disaggregation2(Rational[][] A_, Rational[] B_, List X, int r) {int i = 0;int j = 0;int index = -1;int s = A_[0].length;int n = A_.length;Rational[][] A = new Rational[s][n];Rational[] B = new Rational[s];copy(A_, A);copy(B_, B);while (i < s && j < n) {while (j < n && (index = find(A, i, j, Orient.DOWN)) == -1) {j++;}if (j == n) {break;}if (index != i) {swap(A, B, index, i, j);}for (int k = i+1; k < s; k++) {addRow(A, B, k, i, j);}i++;j++;}i = r - 1;index = r;int[] primary = new int[r];while (i >= 0) {while (i >= 0 && (j = find(A, i, i, Orient.RIGHT)) == -1) {i--;}if (i < 0) {break;}primary[--index] = j;for (int k = 0; k < i; k++) {addRow(A, B, k, i, j);}i--;}index = 0;int[] free = new int[n-r];for (j = 0; j < n; j++) {if (!contains(primary, j)) {free[index++] = j;}}Rational[] gam = new Rational[n];// 这里的自由量不限制取值，这里都取1for (int fi = 0; fi < free.length; fi++) {gam[free[fi]] = Rational.one;}// x[primary[i]] = (b[i] - Σ A[i][free[l]] * ?[free[l]]) / A[i][primary[i]]，i ∈ [0,r)for (int pi = 0; pi < primary.length; pi++) {Rational bi = B[pi];for (int l = 0; l < free.length; l++) {bi = bi.sub(A[pi][free[l]].mul(gam[free[l]]));}gam[primary[pi]] = bi.div(A[pi][primary[pi]]);}Rational[][] eta = new Rational[n-r][n];// 这里取 (随机数,0,...,0)、(0,随机数,0,...,0)...,(0,...,0,随机数)for (int ei = 0; ei < eta.length; ei++) {for (int fi = 0; fi < free.length; fi++) {if (ei == fi) {eta[ei][free[fi]] = new Rational(random.nextInt(50));} else {eta[ei][free[fi]] = Rational.zero;}}for (int pi = 0; pi < primary.length; pi++) {// x[primary[i]] = (-Σ A[i][free[l]] * ?[free[l]]) / A[i][primary[i]]/*Rational rs = Rational.zero;for (int l = 0; l < free.length; l++) {rs = rs.add(A[pi][free[l]].mul(eta[ei][free[l]]));}eta[ei][primary[pi]] = rs.sign().div(A[pi][primary[pi]]);*/// 只有第 l+1 个自由量不为 0 时，上述等式可以简化为：// x[primary[i]] = (-A[i][free[l]] * ?[free[l]]) / A[i][primary[i]]// 若它的值为 1，还可以省略 ?[free[l]eta[ei][primary[pi]] = A[pi][free[ei]].mul(eta[ei][free[ei]]).sign().div(A[pi][primary[pi]]);}}X.add(PARTICULAR, gam);X.add(FUNDAMENTAL, eta);}
}

3. 行向量组

/*** 由于增广行向量是系数行向量的延伸，所以系数行向量组{a1,a2,...,as}的部分组线性无关，则增广行向量组{b1,b2,...,bs}的对应组也线性无关* rank{a1,a2,...,as} <= rank{b1,b2,...,bs}* 设系数行向量组的极大线性无关组为 {a1,a2,...,ar}，则 {b1,b2,...,br} 也线性无关** 从向量组中的其余向量中取出一个向量 aj，使得它的延伸向量 bj 与 b1,...,br 线性无关* 则 rank{a1,a2,...,as} < rank{b1,b2,...,bs}* aj,a1,...,ar 线性相关，aj 可被 a1,...,ar 线性表出，有 aj = k1*a1 +...+ kr*ar* 系数矩阵的第 j 行加上第 1 行的 -k1 倍，...，再加上第 r 行的 -kr 倍，可以转化为零行* 而此时 bj 由于不能被 b1,...,br 线性表出，经过同样的操作，增广矩阵第 j 行的常数项不为 0* 出现 "0=非零数"，无解** 若没有这样的向量 bj，则 {b1,...,br} 是增广行向量组的极大线性无关组，rank{a1,a2,...,as} = rank{b1,b2,...,bs}* bj 可被 b1,...,br 线性表出，有 bj = l1*b1 +...+ lr*br，也有 aj = l1*a1 +...+ lr*ar* 增广矩阵的第 j 行加上第 1 行的 -l1 倍，...，再加上第 r 行的 -lr 倍，可以转化为零行，这行的系数和常数项都为 0* 不会出现 "0=非零数" 的情况，必有解* * 系数矩阵、增广矩阵的行向量组的极大线性无关组中向量的个数不一致，无解；否则有解* * @author cqh* @date 2023/12/19 21:44*/
public class RowDis {public static void main(String[] args) {/*1*x1 + 2*x2 + 3*x3 + 5*x4 + 3*x5 = 26*x1 + 2*x2 + 1*x3 + 4*x4 + 1*x5  = 13*x1 + 1*x2 + 2*x3 + 3*x4 + 4*x5  = 42*x1 + 4*x2 + 1*x3 + 2*x4 + 8*x5  = 5*/// 行向量是 n 维Rational[] a1 = {new Rational(1), new Rational(2), new Rational(3), new Rational(5), new Rational(3)};Rational[] a2 = {new Rational(6), new Rational(2), new Rational(1), new Rational(4), new Rational(1)};Rational[] a3 = {new Rational(3), new Rational(1), new Rational(2), new Rational(3), new Rational(4)};Rational[] a4 = {new Rational(2), new Rational(4), new Rational(1), new Rational(2), new Rational(8)};Rational[] B = {new Rational(2), new Rational(1), new Rational(4), new Rational(5)};Rational[][] A = {a1, a2, a3, a4};List list = disX(A, B);print(list);Rational[] X = getX(list, 10);if (X != null) {System.out.println("要验证的解集 X = " + Arrays.toString(X));verify(A, B, X);}}/*** 验证 X 是否是方程组的解* @param A 系数矩阵* @param B 常数项* @param X 待验证的解*/public static void verify(Rational[][] A, Rational[] B, Rational[] X) {int s = A.length;int n = A[0].length;for (int i = 0; i < s; i++) {Rational r = Rational.zero;for (int j = 0; j < n; j++) {r = r.add(X[j].mul(A[i][j]));}System.out.println(r + " = " + B[i]);if (!r.equals(B[i])) {System.out.println("第 " + (i + 1) + " 个方程结果错误！");}}}/*** 获取方程组的某个解集* @param result 包含解集信息的集合* @param max 无穷多解时，k[i] ∈ [0, max)* @return 方程组的解*/public static Rational[] getX(List result, int max) {Solution solution = (Solution) result.get(SOLUTION);switch (solution) {case UNIQUE :return (Rational[]) result.get(PARTICULAR);case INFINITELY_MANY:Rational[] gam = (Rational[]) result.get(PARTICULAR);Rational[][] eta = (Rational[][]) result.get(FUNDAMENTAL);Rational[] K = new Rational[eta.length];Rational[] X = new Rational[gam.length];int index = 0;random(K, max);System.out.println("令 K = " + Arrays.toString(K));for (int j = 0; j < gam.length; j++) {Rational xj = gam[j];for (int ei = 0; ei < eta.length; ei++) {xj = xj.add(eta[ei][j].mul(K[ei]));}X[index++] = xj;}return X;default:return null;}}private static final Random random = new Random();private static void random(Rational[] arr, int max) {for (int i = 0; i < arr.length; i++) {arr[i] = new Rational(random.nextInt(max));}}/*** 用于查找不为0的元素* 指明查找方向：向右，向下*/public enum Orient {RIGHT, DOWN}/*** 解集情况：无解，唯一解，无穷多解*/public enum Solution {NO, UNIQUE, INFINITELY_MANY}/*** 解集情况*/public static final int SOLUTION = 0;/*** 特解*/public static final int PARTICULAR = 1;/*** 基础解系*/public static final int FUNDAMENTAL  = 2;/*** 打印解集情况* @param solution 包含解集信息的集合*/public static void print(List solution) {Rational[] gam;Rational[][] eta;switch ((Solution)solution.get(SOLUTION)) {case UNIQUE:System.out.print("唯一解：");gam = (Rational[]) solution.get(PARTICULAR);System.out.println(Arrays.toString(gam));break;case INFINITELY_MANY:System.out.println("无穷多解");gam = (Rational[]) solution.get(PARTICULAR);eta = (Rational[][]) solution.get(FUNDAMENTAL);StringBuilder builder = new StringBuilder();int s = gam.length;int n = eta.length;for (int i = 0; i < s; i++) {builder.append("x" + (i+1) + " = ");builder.append(gam[i]);builder.append(" + ");for (int j = 0; j < n; j++) {builder.append(eta[j][i]);builder.append(" * k" + (j+1));if (j != n-1) {builder.append(" + ");}}builder.append("\n");}builder.append("k1,k2,...,kn ∈ Q");System.out.println(builder);break;default:System.out.println("无解");}}private static void checkLength(Rational[][] A, Rational[] B) {int s = A.length;int n = A[0].length;for (int i = 0; i < s; i++) {if (n != A[i].length) {throw new ArrayIndexOutOfBoundsException("向量长度应为" + n + ", 而a" + (i+1) + "长度为" + A[i].length);}}if (B.length != s) {throw new ArrayIndexOutOfBoundsException("B的长度应为" + s);}}/*** 获取矩阵A的行向量组的极大线性无关组* @param A 系数矩阵* @return 矩阵的行向量组的极大线性无关组*/public static List<Rational[]> getMaxLine(Rational[][] A) {int s = A.length;List<Rational[]> maxLine = new ArrayList<>();for (int i = 0; i < s; i++) {if (isIndependent(maxLine, A[i])) {maxLine.add(A[i]);}}return maxLine;}/*** 获取解集情况* @param A 系数矩阵* @param B 常数项* @return 包含解集情况信息的集合*/public static List disX(Rational[][] A, Rational[] B) {checkLength(A, B);int n = A[0].length;List X = new ArrayList(3);int r1 = CRank(A);int r2 = ARank(A, B);if (r1 != r2) {X.add(SOLUTION, Solution.NO);} else {Solution solution = (r1 == n) ? Solution.UNIQUE : Solution.INFINITELY_MANY;X.add(SOLUTION, solution);disaggregation(A, B, X, r1);}return X;}/*** 返回系数矩阵的秩*/private static int CRank(Rational[][] A) {return getMaxLine(A).size();}/*** 返回增广矩阵的秩*/private static int ARank(Rational[][] A, Rational[] B) {Rational[][] enlarge = copy(A, B);return getMaxLine(enlarge).size();}private static void copy(Rational[][] oldArr, Rational[][] newArr) {for (int i = 0; i < oldArr.length; i++) {for (int j = 0; j < oldArr[i].length; j++) {newArr[i][j] = oldArr[i][j];}}}/*** 行数不变，old2 被拷贝到新数组多出的一列* @param old1 系数矩阵* @param old2 常数项* @return 返回增广矩阵*/private static Rational[][] copy(Rational[][] old1, Rational[] old2) {int s = old1.length;int n = old1[0].length + 1;Rational[][] newArr = new Rational[s][n];for (int i = 0; i < s; i++) {for (int j = 0; j < n-1; j++) {newArr[i][j] = old1[i][j];}}for (int i = 0; i < s; i++) {newArr[i][n-1] = old2[i];}return newArr;}/*** 列数不变，行数加一，合并后的矩阵行列互换* @param old1 一个行向量* @param old2 另一个行向量* @return 合并之后再转置的矩阵*/private static Rational[][] copy(List<Rational[]> old1, Rational[] old2) {int s = old1.size() + 1;int n = old1.get(0).length;Rational[][] newArr = new Rational[n][s];for (int i = 0; i < s - 1; i++) {for (int j = 0; j < n; j++) {newArr[j][i] = old1.get(i)[j];}}for (int j = 0; j < n; j++) {newArr[j][s-1] = old2[j];}return newArr;}private static void copy(Rational[] oldArr, Rational[] newArr) {for (int i = 0; i < oldArr.length; i++) {newArr[i] = oldArr[i];}}private static void swap(Rational[][] A, Rational[] B, int index, int i, int j) {Rational temp = B[i];B[i] = B[index];B[index] = temp;swap(A, index, i, j);}private static void swap(Rational[][] A, int index, int i, int j) {int n = A[0].length;for (int l = j; l < n; l++) {Rational temp = A[i][l];A[i][l] = A[index][l];A[index][l] = temp;}}private static void addRow(Rational[][] A, Rational[] B, int index, int i, int j) {Rational d = A[index][j].div(A[i][j]);B[index] = B[index].sub(B[i].mul(d));addRow(A, index, i, j);}private static void addRow(Rational[][] A, int index, int i, int j) {int n = A[0].length;Rational d = A[index][j].div(A[i][j]);for (int l = j; l < n; l++) {A[index][l] = A[index][l].sub(A[i][l].mul(d));}}/*** 将解集信息存入集合中* @param A_ 系数矩阵* @param B_ 常数项* @param X 包含解集信息的集合* @param r 系数矩阵的行向量组的秩*/public static void disaggregation(Rational[][] A_, Rational[] B_, List X, int r) {int i = 0;int j = 0;int index = -1;int s = A_.length;int n = A_[0].length;Rational[][] A = new Rational[s][n];Rational[] B = new Rational[s];copy(A_, A);copy(B_, B);while (i < s && j < n) {while (j < n && (index = find(A, i, j, Orient.DOWN)) == -1) {j++;}if (j == n) {break;}if (index != i) {swap(A, B, index, i, j);}for (int k = i+1; k < s; k++) {addRow(A, B, k, i, j);}i++;j++;}i = r - 1;index = r;int[] primary = new int[r];while (i >= 0) {while (i >= 0 && (j = find(A, i, i, Orient.RIGHT)) == -1) {i--;}if (i < 0) {break;}primary[--index] = j;for (int k = 0; k < i; k++) {addRow(A, B, k, i, j);}i--;}index = 0;int[] free = new int[n-r];for (j = 0; j < n; j++) {if (!contains(primary, j)) {free[index++] = j;}}Rational[] gam = new Rational[n];for (int fi = 0; fi < free.length; fi++) {gam[free[fi]] = Rational.zero;}for (int pi = 0; pi < primary.length; pi++) {gam[primary[pi]] = B[pi].div(A[pi][primary[pi]]);}Rational[][] eta = new Rational[n-r][n];for (int ei = 0; ei < eta.length; ei++) {for (int fi = 0; fi < free.length; fi++) {if (ei == fi) {eta[ei][free[fi]] = Rational.one;} else {eta[ei][free[fi]] = Rational.zero;}}for (int pi = 0; pi < primary.length; pi++) {eta[ei][primary[pi]] = A[pi][free[ei]].sign().div(A[pi][primary[pi]]);}}X.add(PARTICULAR, gam);X.add(FUNDAMENTAL, eta);}private static boolean contains(int[] arr, int num) {for (int i = 0; i < arr.length; i++) {if (num == arr[i]) {return true;}}return false;}/*** 根据模式查找，返回非零元素的下标* @param A 待查的矩阵* @param i 起始位置的行标* @param j 起始位置的列标* @param o 查找模式。down是向下查找，行标变；right是向右查找，列标变* @return 返回非零元素的下标。向下查找时，返回非零元素的行标；向右查找时，返回非零元素的列标。*         若没有查找到，返回-1*/public static int find(Rational[][] A, int i, int j, Orient o) {int s = A.length;int n = A[0].length;switch (o) {case DOWN:while (i < s) {if (!Rational.zero.equals(A[i][j])) {break;}i++;}if (i == s) {return -1;}return i;case RIGHT:while (j < n) {if (!Rational.zero.equals(A[i][j])) {break;}j++;}if (j == n) {return -1;}return j;default:return -1;}}/*** 若 a 与向量组 maxLine 线性无关，则返回 true* @param maxLine 线性无关组* @param a 向量* @return 若向量组 a,maxLine 线性无关，则返回 true，否则返回 false*/public static boolean isIndependent(List<Rational[]> maxLine, Rational[] a) {boolean isZero = isZero(a);if (isZero) {return false;}boolean isEmpty = maxLine == null || maxLine.isEmpty();if (isEmpty)  {return true;}int s = maxLine.size() + 1;int n = maxLine.get(0).length;// 超过 n 个的 n 维向量必线性相关if (s > n) {return false;}/*到达这里时，s 必然 <= nA 是 n 行 s 列，若不想转置，可以将下面的计算改为互换两列，一列加另一列的倍数作用是将多出的 n-s 列化为零行，然后取前 s 列，计算行列式*/Rational[][] A = copy(maxLine, a);int i = 0;int j = 0;while (i < n && j < s) {if (Rational.zero.equals(A[i][j])) {for (int k = i + 1; k < n; k++) {if (!Rational.zero.equals(A[k][j])) {swap(A, k, i, j);break;}}}if (Rational.zero.equals(A[i][j])) {return false;}for (int k = i+1; k < n; k++) {addRow(A, k, i, j);}i++;j++;}Rational l = Rational.one;for (i = 0; i < s; i++) {l = l.mul(A[i][i]);}if (Rational.zero.equals(l)) {return false;}return true;}/*** 如果向量 a 的每个分量都为 0，则返回 true* 规定 {} 为零向量* @param a 向量* @return 若向量的每个元素都为0，或向量长度为0，则返回 true；否则返回 false*/public static boolean isZero(Rational[] a) {for (int i = 0; i < a.length; i++) {if (!Rational.zero.equals(a[i])) {return false;}}return true;}
}

1. 行列式

import java.util.Arrays;/*** 给出有理数域上n个方程的n元线性方程组的唯一解（若有）** @author cqh* @date 2023/12/09 14:03*/
/*
有理数域上n个方程的n元线性方程组有唯一解 <=> 系数矩阵A的行列式不等于零
可给出唯一解：{x1,x2,...xn}, xj = |Bj| / |A|，Bj是将A的第j列换成常数项, j = 1,2,...,n
限制：(1)方程个数必须与未知量个数相等(2)只能判断是否有唯一解，当不是唯一解时，无法分辨方程组是无解还是无穷多解用处之一：用来判断向量组是线性无关还是相关的
无解是阶梯型方程组出现了 "0=d" 这种情况(d为非零数)，但行列式并不囊括常数项，无法判断
当常数项都为 0 时，方程必定有解，所以这种特殊情形时，行列式可以判断是唯一解(零解)还是无穷多解(非零解)x1*a1 +...+ xn*an + l*b = 0，若|A|≠0，则只有零解(全为0)，a1,...,an,b线性无关
若|A|=0，则有非零解(不全为0)，a1,...,an,b线性相关x1*a1 +...+ xn*an = b 有解 <=> 存在一组数使得 k1*a1 +...+ kn*an = b
（称作 b 可由 a1,...,an 线性表出）
=> k1*a1 +...+ kn*an - b = 0 => a1,...,an,b线性相关则它的逆否命题成立，若a1,...,an,b线性无关 => x1*a1 +...+ xn*an = b 无解
但 a1,...,an,b 相关，无法推出方程组有解还是无解若 a1,...,ar 线性无关，a1,...,ar,b 线性相关 <=> b 可由 a1,...,ar 线性表出
存在不全为0的数 k1,...,kr,l，使得 k1*a1+...+kr*ar+l*b = 0 成立
假设 l=0，则 k1,...,kr 不全为0，同时 k1*a1+...+kr*ar = 0，推出 a1,...,ar 线性相关
矛盾，假设错误，所以 l≠0
b = -(k1/l)*a1-...-(kr/l)*ar
b 可由 a1,...,ar 线性表出，即 x1*a1 +...+ xr*ar = b 有解所以如果 a1,...,an 线性相关，取出它的线性无关组 a1,...,ar，这个无关组能够表出向量组的所有向量
如果 b 能由 a1,...,an 表出，则一定能由 a1,...,ar 表出所以问题转化为，方程组有解 <=> a1,...,ar,b 线性相关
方程组无解 <=> a1,...,ar,b 线性无关所以在另一个类中，主要考虑如何取出能够表出所有向量的线性无关组*/
public class DisX {public static void main(String[] args) {/*5x1 + 1x2 = 13;2x1 + 3x2 = 13;求 x1、x2*/Rational[][] A = {{new Rational(5), new Rational(1)},{new Rational(2), new Rational(3)},};Rational[] B = {new Rational(13), new Rational(13)};// X = (x1, x2);Rational[] X = disX(A, B);// 修改成错误的解集 (3, -2)，使其不满足第2个方程// X[0] = new Rational(3);// X[1] = new Rational(-2);if (X != null) {System.out.println("唯一解：" + Arrays.toString(X));verify(A, B, X);} else {System.out.println("本方程组无解或无穷多解");}}/*** 当有唯一解时，验证解集是否正确* @param A 系数矩阵* @param B 常数项* @param X 要验证的解集*/public static void verify(Rational[][] A, Rational[] B, Rational[] X) {int n = A.length;// 将解集(x1,x2,...,x3)代入方程中验证for (int i = 0; i < n; i++) {Rational r = Rational.zero;for (int j = 0; j < n; j++) {r = r.add(A[i][j].mul(X[j]));}System.out.println(r + " = " + B[i]);if (!r.equals(B[i])) {System.out.println("第 " + (i + 1) + " 个方程结果错误！");}}}// 确保 A 是 n 级矩阵，B 的长度为 n，不满足条件抛出ArrayIndexOutOfBoundsExceptionprivate static void checkLength(Rational[][] A, Rational[] B) {int n = A.length;for (int i = 0; i < n; i++) {if (n != A[i].length) {throw new ArrayIndexOutOfBoundsException("A的第" + (i+1) + "行长度应为" + n);}}if (n != B.length) {throw new ArrayIndexOutOfBoundsException("B的长度应为" + n);}}/*** 返回方程的解集* @param A 系数矩阵* @param B 常数项* @return 若无解或无穷多解，返回 null*/public static Rational[] disX(Rational[][] A, Rational[] B) {checkLength(A, B);int n = A.length;// 求 A 的行列式Rational detA = detA(A);// 如果 |A| = 0，返回 nullif (detA.equals(Rational.zero)) {return null;}// |A| ≠ 0，返回解集 {x1,x2,...,xn}Rational[] X = new Rational[n];for (int index = 0; index < n; index++) {// 将 A 的第 index 列换成常数项得到矩阵 BiRational[][] Bi = new Rational[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (j == index) {Bi[i][j] = B[i];} else {Bi[i][j] = A[i][j];}}}X[index] = detA(Bi).div(detA);}return X;}/*** 拷贝数组中的元素到一个新数组中* @param old 要拷贝的数组* @return 新数组*/public static Rational[][] copy(Rational[][] old) {Rational[][] newArr = new Rational[old.length][];for (int i = 0; i < old.length; i++) {newArr[i] = new Rational[old[i].length];for (int j = 0; j < old[i].length; j++) {newArr[i][j] = old[i][j];}}return newArr;}/*** 将矩阵的第 k 行与第 i 行对换* @param A 系数矩阵* @param k 被交换的一行的下标* @param i 被交换的另一行的下标*/public static void swap(Rational[][] A, int k, int i) {Rational[] temp = A[k];A[k] = A[i];A[i] = temp;}// 将 A 的第 k 行与第 i 行对换，起始位置从第 j 个元素开始@Deprecatedprivate static void swap2(Rational[][] A, int k, int i, int j) {for (int l = j; l < A.length; l++) {Rational temp = A[k][l];A[k][l] = A[i][l];A[i][l] = temp;}}/*** 求矩阵的行列式* @param A_ 系数矩阵* @return 系数矩阵的行列式*/public static Rational detA(Rational[][] A_) {int i = 0;int j = 0;Rational l = Rational.one;int n = A_.length;// 创建新的数组 A，以免换行时影响原数组 A_Rational[][] A = copy(A_);while (i < n && j < n) {// 如果第 i 行第 j 列为 0，则在第 2、3、...n 行中寻找这列不为 0 的元素，并记录行标 k// 若找到，则将第 k 行和第 i 行替换if (A[i][j].equals(Rational.zero)) {for (int k = i + 1; k < n; k++) {if (!A[k][j].equals(Rational.zero)) {swap(A, k, i);// 两行互换后，行列式变号l = l.sign();break;}}}// 说明这一列元素全为0，行列式值为0if (A[i][j].equals(Rational.zero)) {return Rational.zero;}// 使 i 之后的所有行加上第 i 行的 mul 倍，使第 k 行第 j 列的元素为 0for (int k = i + 1; k < n; k++) {Rational mul = A[k][j].div(A[i][j]).sign();addRow(A, k, i, j, mul);}i++;j++;}// 上述操作后，A已转为上三角形行列式，将主对角线上的n个元素相乘for (i = 0; i < n; i++) {l = l.mul(A[i][i]);}return l;}/*** 将矩阵的第 k 行元素加上第 i 行的 mul 倍，从第 j 个元素开始* @param A 系数矩阵* @param k 被加的一行* @param i 这行的倍数要加到另一行上* @param j 起始元素下标* @param multiple 指定倍数*/public static void addRow(Rational[][] A, int k, int i, int j, Rational multiple) {// 第 k 行加上第 i 行的 multiple 倍for (int l = j; l < A.length; l++) {A[k][l] = A[k][l].add(A[i][l].mul(multiple));}}
}

4. 有理数

/*** 有理数** @author cqh* @date 2023/12/10 9:35*/
// 以两个整数之比表示有理数
public class Rational {/*** 有理数0*/public final static Rational zero = new Rational(0);/*** 有理数1*/public final static Rational one = new Rational(1);/*** 有理数-1*/public final static Rational negativeOne = new Rational(-1);// 分子private int numerator;// 分母private int denominator;/*** 构建值为 numerator 的有理数* @param numerator 分子*/public Rational(int numerator) {this.numerator = numerator;this.denominator = 1;}/*** 构建值为 numerator/denominator 的有理数* @param numerator 分子* @param denominator 分母*/public Rational(int numerator, int denominator) {if (denominator == 0) {throw new ArithmeticException("分母不能为0！");}if (numerator == Integer.MIN_VALUE || denominator == Integer.MIN_VALUE) {throw new ArithmeticException("整数取值超过范围！");}// 使分母为正数if (denominator < 0) {numerator = -numerator;denominator = -denominator;}int gcd = gcd(numerator, denominator);this.numerator = numerator/gcd;this.denominator = denominator/gcd;}/*** 返回值为 this+r2 的有理数* @param r2 加数* @return 返回值为 this+r2 的有理数*/public Rational add(Rational r2) {int d1 = this.denominator;int d2 = r2.denominator;int d3 = lcm(d1, d2);int n3 = (d3 / d1) * this.numerator + (d3 / d2) * r2.numerator;Rational r3 = new Rational(n3, d3);return r3;}/*** 返回值为 this-r2 的有理数* @param r2 减数* @return 返回值为 this-r2 的有理数*/public Rational sub(Rational r2) {int d1 = this.denominator;int d2 = r2.denominator;int d3 = lcm(d1, d2);int n3 = (d3 / d1) * this.numerator - (d3 / d2) * r2.numerator;Rational r3 = new Rational(n3, d3);return r3;}/*** 返回值为 this*r2 的有理数* @param r2 乘数* @return 返回值为 this*r2 的有理数*/public Rational mul(Rational r2) {int n1 = this.numerator;int d1 = this.denominator;int n2 = r2.numerator;int d2 = r2.denominator;// 分式1的分子与分式2的分母进行约分int g1 = gcd(n1, d2);int n31 = n1 / g1;int d32 = d2 / g1;// 分式1的分母与分式2的分子进行约分int g2 = gcd(n2, d1);int n32 = n2 / g2;int d31 = d1 / g2;// 分子与分子相乘得到另一个分式的分子long n3 = (long)n31 * (long)n32;long d3 = (long)d31 * (long)d32;if (n3 > Integer.MAX_VALUE || d3 > Integer.MAX_VALUE) {throw new ArithmeticException("两数相乘溢出！");}return new Rational((int)n3, (int)d3);}/*** 返回值为 this/r2 的有理数* @param r2 除数* @return 返回值为 this/r2 的有理数*/public Rational div(Rational r2) {if (r2.numerator == 0) {throw new ArithmeticException("分母不能为0！");}// 除以 r2 等于乘以 r2 的倒数return this.mul(new Rational(r2.denominator, r2.numerator));}// 返回值为 this/r2 的有理数@Deprecatedprivate Rational div2(Rational r2) {if (r2.numerator == 0) {throw new ArithmeticException("分母不能为0！");}int n1 = this.numerator;int d1 = this.denominator;int n2 = r2.numerator;int d2 = r2.denominator;int g1 = gcd(n1, n2);int n31 = n1 / g1;int d32 = n2 / g1;int g2 = gcd(d1, d2);int n32 = d2 / g2;int d31 = d1 / g2;long n3 = (long)n31 * (long)n32;long d3 = (long)d31 * (long)d32;if (n3 > Integer.MAX_VALUE || d3 > Integer.MAX_VALUE) {throw new ArithmeticException("两数相乘溢出！");}return new Rational((int)n3, (int)d3);}/*** 返回 this 的相反数* @return 不改变 this 的符号，而是返回它的相反数*/public Rational sign() {if (Rational.zero.equals(this)) {return Rational.zero;}if (Rational.one.equals(this)) {return Rational.negativeOne;}if (Rational.negativeOne.equals(this)) {return Rational.one;}return new Rational(-this.numerator, this.denominator);}@Overridepublic String toString() {if (this.numerator == 0) {return "0";}if (this.denominator == 1) {return "" + numerator;}return numerator + "/" + denominator;}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Rational rational = (Rational) o;return numerator == rational.numerator && denominator == rational.denominator;}// 返回 a 与 b 的最小公倍数private static int lcm(int a, int b) {if (a == 0 || a == b) {return Math.abs(a);} else if (b == 0) {return 0;}int n = gcd(a, b);long result = Math.abs((long)a * (long)b);result = result / n;if (result > Integer.MAX_VALUE) {throw new ArithmeticException("两数相乘溢出！");}return (int)result;}// 返回 a 与 b 的最大公因数private static int gcd(int a, int b) {if (a == 0 || a == b) {return Math.abs(b);} else if (b == 0) {return Math.abs(a);}int m = Math.abs(a);int n = Math.abs(b);if (m < n) {int temp = m;m = n;n = temp;}for (int r = m % n; r != 0; r = m % n) {m = n;n = r;}return n;}
}

这篇关于判断数域上s个方程的n元线性方程组有无解，有解时解集的结构的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---