# Solving A\*x=b in Nemo

**URL:** <https://discourse.julialang.org/t/solving-a-x-b-in-nemo/101051>\
**Category:** General Usage\
**Tags:** matrices, convert, nemo\
**Created:** [July 1, 2023, 1:04pm UTC](https://discourse.julialang.org/t/solving-a-x-b-in-nemo/101051 "2023-07-01T13:04:09Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![blociss](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/blociss/32/16421_2.png) [@blociss](https://discourse.julialang.org/u/blociss)\
**Post date:** [July 1, 2023, 1:04pm UTC](https://discourse.julialang.org/t/solving-a-x-b-in-nemo/101051/1 "2023-07-01T13:04:09Z")

</div>

Let `A = [1 0 0; 0 1 1; 0 3 0; 0 0 1]`

a matrix of type `4×3 Matrix{QQFieldElem}: `  
and `Q=[2 ,-3 , 1, 1]` of type `4-element Vector{QQFieldElem}: `  
My goal is to compute A \setminus Q but I got error

> MethodError: no method matching abs2(::QQFieldElem)

I try to convert `4×3 Matrix{QQFieldElem}:` into `4×3 Matrix{Int64}:` so I can use _LinearAlgebra_ package but no success.  
Any ideal how to compute this.

---

<div class="post-metadata">

**Author:** ![greatpet](https://avatars.discourse-cdn.com/v4/letter/g/e495f1/32.png) [@greatpet](https://discourse.julialang.org/u/greatpet)\
**Post date:** [July 1, 2023, 8:12pm UTC](https://discourse.julialang.org/t/solving-a-x-b-in-nemo/101051/2 "2023-07-01T20:12:31Z")

</div>

You’re trying to find a length-3 vector `X` such that `A * X == Q`. In this case, you can check by hand that no solution exists, because the system is over-determined. If you were doing this over floating-point numbers, it makes sense to talk about a “closest” solution, but this is not a natural thing for rational numbers or integers. If you really need to do this, convert the matrix and vector to Float64.

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [July 1, 2023, 8:45pm UTC](https://discourse.julialang.org/t/solving-a-x-b-in-nemo/101051/3 "2023-07-01T20:45:04Z")

</div>

> [@greatpet](#):
>
> If you were doing this over floating-point numbers, it makes sense to talk about a “closest” solution, but this is not a natural thing for rational numbers or integers. If you really need to do this, convert the matrix and vector to Float64.

You’re assuming @blociss wants the closest solution, however what they want is not at all clear.

@blociss if you’re looking for an exact solution, as opposed to the closest one, look here:

> [@How to exactly solve large overdetermined systems of linear equations](https://discourse.julialang.org/t/how-to-exactly-solve-large-overdetermined-systems-of-linear-equations/86710/):
>
> Suppose I have, e.g., 250 linear equations with Rational{BigInt} coefficients, with 150 variables. If the system is inconsistent I want to know about it, otherwise I want the exact solution. Is there an easier way than writing my own Gaussian elimination? This won’t run often, so I’m not concerned with long runtimes.

---

<div class="post-metadata">

**Author:** ![blociss](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/blociss/32/16421_2.png) [@blociss](https://discourse.julialang.org/u/blociss)\
**Post date:** [July 1, 2023, 10:23pm UTC](https://discourse.julialang.org/t/solving-a-x-b-in-nemo/101051/4 "2023-07-01T22:23:34Z")

</div>

What I want is to convert `QQFieldElem` into `Int64` element.  
I got closed solution when the matrix and vector are of type `Int64`.

---

<div class="post-metadata">

**Author:** ![PeterSimon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petersimon/32/25193_2.png) [@PeterSimon](https://discourse.julialang.org/u/PeterSimon)\
**Post date:** [July 2, 2023, 3:11am UTC](https://discourse.julialang.org/t/solving-a-x-b-in-nemo/101051/5 "2023-07-02T03:11:05Z")

</div>

Edit: As pointed out by @thofma, the method below is brittle and should not be used. See [this](https://discourse.julialang.org/t/solving-a-x-b-in-nemo/101051/8) post for the correct way.

```julia
julia> function conv2int(A::Array{QQFieldElem})
           all(x -> x.den == 1, A) || error("A not an integer-valued matrix")
           return map(x -> x.num, A)
       end
conv2int (generic function with 1 method)

julia> A = QQFieldElem[1 0 0; 0 1 1; 0 3 0; 0 0 1]
4×3 Matrix{QQFieldElem}:
 1 0 0
 0 1 1
 0 3 0
 0 0 1

julia> Aint = conv2int(A)
4×3 Matrix{Int64}:
 1 0 0
 0 1 1
 0 3 0
 0 0 1

```

---

<div class="post-metadata">

**Author:** ![thofma](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/thofma/32/1691_2.png) [@thofma](https://discourse.julialang.org/u/thofma)\
**Post date:** [July 2, 2023, 5:34am UTC](https://discourse.julialang.org/t/solving-a-x-b-in-nemo/101051/6 "2023-07-02T05:34:22Z")

</div>

The functions for solving or checking solvability are `can_solve` and `can_solve_with_solution`. Only works with matrices though, so your example would look like:

```julia
julia> A = QQ[1 0 0; 0 1 1; 0 3 0; 0 0 1]
[1 0 0]
[0 1 1]
[0 3 0]
[0 0 1]

julia> Q = [2 ,-3 , 1, 1]
4-element Vector{Int64}:
  2
 -3
  1
  1

julia> B = matrix(QQ, 4, 1, Q)
[2]
[-3]
[1]
[1]

julia> can_solve(A, B)
false

```

See also the docstring of `can_solve`.

(Here is how it would look like to compute a solution in case one exists:

```julia
julia> B = matrix(QQ, 4, 1, [1, 0, 0, 0])
[1]
[0]
[0]
[0]

julia> can_solve_with_solution(A, B)
(true, [1; 0; 0])

```

)

---

<div class="post-metadata">

**Author:** ![blociss](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/blociss/32/16421_2.png) [@blociss](https://discourse.julialang.org/u/blociss)\
**Post date:** [July 2, 2023, 7:11pm UTC](https://discourse.julialang.org/t/solving-a-x-b-in-nemo/101051/7 "2023-07-02T19:11:56Z")

</div>

So this doesn’t work if `A` and `B` are of type `Matrix{QQFieldElem}`?

---

<div class="post-metadata">

**Author:** ![thofma](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/thofma/32/1691_2.png) [@thofma](https://discourse.julialang.org/u/thofma)\
**Post date:** [July 3, 2023, 7:30am UTC](https://discourse.julialang.org/t/solving-a-x-b-in-nemo/101051/8 "2023-07-03T07:30:06Z")

</div>

Yes. By the way, if you want to convert to `Matrix{Int}`, the correct way would be

```julia
julia> A = QQFieldElem[1 0 0; 0 1 1; 0 3 0; 0 0 1]
4×3 Matrix{QQFieldElem}:
 1 0 0
 0 1 1
 0 3 0
 0 0 1

julia> map(x -> Int(ZZ(x)), A)
4×3 Matrix{Int64}:
 1 0 0
 0 1 1
 0 3 0
 0 0 1

```

The version with `x.num` will give (silently) wrong results:

```julia
julia> A = QQFieldElem[1 0 0; 0 1 1; 0 3 0; 0 0 18446744073709551615]
4×3 Matrix{QQFieldElem}:
 1 0 0
 0 1 1
 0 3 0
 0 0 18446744073709551615

julia> Aint = conv2int(A)
4×3 Matrix{Int64}:
 1 0 0
 0 1 1
 0 3 0
 0 0 4611686018537972628

```