The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote
Let AX=B be a system of n linear equations in n unknown with integer coefficient and the components of B are all integer. Consider the following



(3)Solution X has integer entries

(4)Solution X does not have all integer entries

For the given system of linear equations which one of the following is correct?

(a)Only 3 unconditionally holds true.

(b)If 1, then 3 holds true

(c)If 1, then 4 holds true

(d)If 2, then 3 holds true

I think (d) should be the answer.
asked in Linear Algebra by Boss (25.4k points) | 94 views
why d???

just put any number which is same in all rows and columns of matrix so det. is 1/3 in all places it will be 0

i think c correct

what is A and what is X??
@ Deepanshu

why C?

just take the equation x-y=0,y=1. solving it, we will get solutions as integer. 1,1

we can also take other counter examples.

aambazinga whats problem with c ?????

@srestha-A is the coefficient matrix. X is the solution vector

1 Answer

+1 vote

By Cramer's rule, we know that element $x_i$ of solution matrix $X$ can found by the following formula:


assuming $det(A)=1$ , we get $x_i=det(A_i)$    

(recall when applying cramer's rule, $A_i$ is a matrix formed by replacing the $i^{th}$ column in matrix $A$ with column matrix $B$)

It is already given that elements of $B$ are integral and all coefficients in equations are integral therefore elements of matrix $A$ are integral as well. As $A_i$ is made from elements of $A$ and $B$, therefore it's elements are integral as well.

Determinant of a matrix with integral elements will always be integral (you can prove this yourself) therefore $det(A_i)$ will also be integral. As $x_i= det(A_i)$ therefore $x_i$ is integral as well.

Hence we have shown that all elements of solution matrix  X will be integral when $det(A)=1$. 

So answer is (b)


answered by Active (1.4k points)
bro whts problem with c?????
What you are stating is that if det(A) =1 then it does not have all integral solutions, which is exactly opposite of what is proved above. @aambazinga has already shown you a counter example in his comment.
I think it can be (d) also.

if det(A)=0, means the matrix is singular.

Means the rows and columns of A are dependent and hence I can design a non-zero vector X such that AX=O the solution to the null space and if B contains all zeroes which are integer, AX=O holds.

Related questions

0 votes
1 answer
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,413 questions
53,595 answers
70,878 users