Solve Matrix Inequality Ax ≤ b, nxn A with Solution Exists

In summary: WV3c29uLCBBIHwgYiwgYXN1bW5pbmcgQSBpcyBueG4gYW5kIHNvbHV0aW9uIGV4aXN0cwogICMgZ3JhZCBzdXRwb3J0ZWQgcmVhc29uYXJ5aW5nIGl0IHRvOgogIDEgQ3JlYXRlIGZvciBhcHBseSBzZWNvbmQgKjogY3JlYXRlIHRoZToKICAgQXgtYm91bmQsIHog
  • #1
muzak
44
0

Homework Statement


Ax ≤ b, assuming A is nxn and solution exists


Homework Equations





The Attempt at a Solution


I don't know of any concrete methods offhand. A grad student suggested rearranging it to:
Ax - b ≤ 0, zero vector

Then I don't know where to go from here. I was thinking of multiplying by [itex]x^{T}[/itex] to get [itex]x^{T}Ax - x^{T}b ≤ 0[/itex] , 0 a scalar now. Is this a valid method? If not, I wouldn't mind any direction to theorems that say otherwise. Then I was thinking of solving for the null space of A and finding some other method to make [itex]x^{T}b[/itex] ≥ 0 (would also like some literature or reference to methods involving this operation).

aye or nay, if nay, can someone suggest the general accepted methods and perhaps the name of what this kind of problem is. Thanks in advance.
 
Physics news on Phys.org
  • #2
muzak said:

Homework Statement


Ax ≤ b, assuming A is nxn and solution exists


Homework Equations





The Attempt at a Solution


I don't know of any concrete methods offhand. A grad student suggested rearranging it to:
Ax - b ≤ 0, zero vector

Then I don't know where to go from here. I was thinking of multiplying by [itex]x^{T}[/itex] to get [itex]x^{T}Ax - x^{T}b ≤ 0[/itex] , 0 a scalar now. Is this a valid method? If not, I wouldn't mind any direction to theorems that say otherwise. Then I was thinking of solving for the null space of A and finding some other method to make [itex]x^{T}b[/itex] ≥ 0 (would also like some literature or reference to methods involving this operation).

aye or nay, if nay, can someone suggest the general accepted methods and perhaps the name of what this kind of problem is. Thanks in advance.

This is a standard linear inequality question. Typically we first convert to an equality by adding *slack* variables: if s_1, s_2,...,s_n are slack variables, we require s_1 ≥ 0, s_2 ≥ 0, ..., s_n ≥ 0, and we can write BX = 0, where B = [A,I] (I = nxn identity matrix) and X = [x_1, x_2, ..., x_n, s_1, s_2, ...,s_n}^T. Now we need to look for feasible basic solutions; these are obtained by selecting n linearly-independent columns of the matrix B (called basic columns), and solving for the corresponding basic variables in terms of the non-basic variables, then setting the non-basic variables to zero. If all of the basic solutions are infeasible (that is, have at least one s_i < 0) the original problem is infeasible; otherwise, there exists at least one basic solution that is feasible (and maybe many such points). All of this is part of the subject of Linear Programming.

RGV
 

FAQ: Solve Matrix Inequality Ax ≤ b, nxn A with Solution Exists

What is a matrix inequality?

A matrix inequality is a mathematical statement that compares two matrices using the symbols <, >, ≤, or ≥. It is used to express relationships between matrices, such as which one is larger or smaller, or if they are equal.

How do you solve a matrix inequality?

To solve a matrix inequality, you first need to determine the dimensions of the matrices involved. Then, you can use various methods such as Gaussian elimination or graphing to determine the solution set. The solution set will be a range of values that satisfy the inequality.

What is the purpose of the matrix A in the inequality Ax ≤ b?

The matrix A represents the coefficients of the variables in the inequality. It is used to determine the relationships between the variables and the values that satisfy the inequality.

Can a matrix inequality have multiple solutions?

Yes, a matrix inequality can have multiple solutions. This is because the solution set can contain a range of values that satisfy the inequality, rather than a single specific value.

Why is it important to determine if a solution exists for a matrix inequality?

Determining if a solution exists for a matrix inequality is important because it tells us if there is a set of values that satisfies the inequality. If a solution exists, it means that the inequality is true for certain values, which can provide valuable information in various mathematical and scientific applications.

Similar threads

Replies
3
Views
949
Replies
8
Views
3K
Replies
9
Views
859
Replies
13
Views
2K
Replies
6
Views
839
Replies
4
Views
3K
Back
Top